检查两个字符串是否几乎相等

难度: Easy

如果两个字符串 word1 和 word2 中从 'a' 到 'z' 每一个字母出现频率之差都 不超过 3 ，那么我们称这两个字符串 word1 和 word2 几乎相等 。

给你两个长度都为 n 的字符串 word1 和 word2 ，如果 word1 和 word2 几乎相等 ，请你返回 true ，否则返回 false 。

一个字母 x 的出现频率指的是它在字符串中出现的次数。

示例 1：

输入：word1 = "aaaa", word2 = "bccb"
输出：false
解释：字符串 "aaaa" 中有 4 个 'a' ，但是 "bccb" 中有 0 个 'a' 。
两者之差为 4 ，大于上限 3 。

示例 2：

输入：word1 = "abcdeef", word2 = "abaaacc"
输出：true
解释：word1 和 word2 中每个字母出现频率之差至多为 3 ：
- 'a' 在 word1 中出现了 1 次，在 word2 中出现了 4 次，差为 3 。
- 'b' 在 word1 中出现了 1 次，在 word2 中出现了 1 次，差为 0 。
- 'c' 在 word1 中出现了 1 次，在 word2 中出现了 2 次，差为 1 。
- 'd' 在 word1 中出现了 1 次，在 word2 中出现了 0 次，差为 1 。
- 'e' 在 word1 中出现了 2 次，在 word2 中出现了 0 次，差为 2 。
- 'f' 在 word1 中出现了 1 次，在 word2 中出现了 0 次，差为 1 。

示例 3：

输入：word1 = "cccddabba", word2 = "babababab"
输出：true
解释：word1 和 word2 中每个字母出现频率之差至多为 3 ：
- 'a' 在 word1 中出现了 2 次，在 word2 中出现了 4 次，差为 2 。
- 'b' 在 word1 中出现了 2 次，在 word2 中出现了 5 次，差为 3 。
- 'c' 在 word1 中出现了 3 次，在 word2 中出现了 0 次，差为 3 。
- 'd' 在 word1 中出现了 2 次，在 word2 中出现了 0 次，差为 2 。

提示：

n == word1.length == word2.length
1 <= n <= 100
word1 和 word2 都只包含小写英文字母。

Submission

运行时间: 19 ms

内存: 15.9 MB

class Solution:
    def checkAlmostEquivalent(self, word1: str, word2: str) -> bool:
        A = [0] * 26
        for char in word1: A[ord(char) - ord("a")] += 1
        for char in word2: A[ord(char) - ord("a")] -= 1  # Fixed the offset
        return not any([(f < -3 or f > 3) for f in A])

Explain

此题解的思路是使用一个大小为26的数组A来统计两个字符串中每个字母的频率差异。遍历字符串word1时，对应字母在数组A中的值增加；遍历字符串word2时，相应字母在数组A中的值减少。这样，数组A最终保存了两个字符串中每个字母的净出现次数差。最后，检查数组A中的每个值是否都在-3到3的范围内，若是，则返回true，表示两个字符串几乎相等；若不是，则返回false。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def checkAlmostEquivalent(self, word1: str, word2: str) -> bool:
        A = [0] * 26  # 创建一个大小为26的数组，用于统计字母频率差
        for char in word1: A[ord(char) - ord('a')] += 1  # 遍历word1，增加频率
        for char in word2: A[ord(char) - ord('a')] -= 1  # 遍历word2，减少频率
        return not any([(f < -3 or f > 3) for f in A])  # 检查所有频率差是否都在[-3, 3]之间

Explore

在处理仅涉及英文字母的字符串时，使用大小为26的数组来记录字符频率是一个效率高且空间占用低的方法。这是因为数组允许通过简单的索引操作即可实现快速访问和更新，其时间复杂度为O(1)。相比之下，哈希表虽然灵活且可扩展到更广泛的字符集，但在此场景下它可能涉及较高的哈希计算和冲突解决成本，且通常空间占用更大。因此，对于固定且有限的数据范围（如26个英文字母），使用数组是更优的选择。

使用列表推导配合any函数是一种简洁的方法来检查数组中是否存在不符合条件的元素。然而，这种方法首先生成一个布尔列表，然后再进行迭代检查，可能在空间效率上不是最优的。一个更优的替代方案是使用简单的循环来直接检查每个元素，这样可以在找到第一个不符合条件的元素时立即停止检查，避免额外的空间使用和完整的列表遍历。例如：`for f in A: if f < -3 or f > 3: return false`，最后返回true。这样做提高了效率且保持了良好的可读性。

代码中使用`ord(char) - ord('a')`来获取字符相对于'a'的位置是一种在多数支持字符编码函数的编程语言中有效的方法（如Python, Java, C++）。然而，并非所有编程语言均内置这类函数，或者字符编码方式可能有所不同。在不支持的环境中，可以使用字符与其ASCII码的映射表或字典来实现类似的功能。例如，在JavaScript中，可以使用`char.charCodeAt(0) - 'a'.charCodeAt(0)`来达到同样的效果。

在实际编码过程中，确实有可能因为疏忽或错误理解条件而错误地实现这种边界检查。例如，可能会错误地编写为`f <= -3 or f >= 3`，这会导致边界条件处理错误。此外，不同编程语言中的逻辑运算符优先级不同可能也会引起问题。为避免这些错误，建议在实现逻辑判断时增加单元测试，确保所有边界条件都被恰当处理。此外，对于复杂的条件表达式，使用括号明确优先级是一个好习惯，能够增加代码的清晰度和准确性。