Easy

题目描述

如果两个字符串 word1 和 word2 中每个字母 ‘a’ 到 ‘z’ 的出现频次差值最多为 3，则认为这两个字符串几乎相等。

给定两个长度均为 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

约束条件：

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

解题思路

解题思路

这道题的核心是统计两个字符串中每个字符的出现频次，然后比较对应字符频次的差值是否都不超过 3。

方法一：哈希表统计（推荐）

  1. 分别统计两个字符串中每个字符的出现频次
  2. 遍历所有可能的字符（‘a’ 到 ‘z’），计算每个字符在两个字符串中出现频次的绝对差值
  3. 如果任意字符的频次差值超过 3，返回 false；否则返回 true

方法二：数组计数优化

由于题目限定只有小写字母，可以使用长度为 26 的数组代替哈希表，通过 ch - 'a' 计算索引，空间效率更高。

方法三：单次遍历差值统计

可以在一次遍历中同时处理两个字符串，用一个数组记录字符频次差值，word1 中的字符 +1，word2 中的字符 -1，最后检查所有差值的绝对值是否都不超过 3。

时间复杂度主要是 O(n)，其中 n 是字符串长度。由于需要检查固定的 26 个字母，常数项较小。

代码实现

class Solution {
public:
    bool checkAlmostEquivalent(string word1, string word2) {
        vector<int> count(26, 0);
        
        // 统计频次差值：word1中的字符+1，word2中的字符-1
        for (char c : word1) {
            count[c - 'a']++;
        }
        for (char c : word2) {
            count[c - 'a']--;
        }
        
        // 检查所有字符的频次差值是否都不超过3
        for (int diff : count) {
            if (abs(diff) > 3) {
                return false;
            }
        }
        
        return true;
    }
};

class Solution:
    def checkAlmostEquivalent(self, word1: str, word2: str) -> bool:
        count = [0] * 26
        
        # 统计频次差值：word1中的字符+1，word2中的字符-1
        for c in word1:
            count[ord(c) - ord('a')] += 1
        for c in word2:
            count[ord(c) - ord('a')] -= 1
        
        # 检查所有字符的频次差值是否都不超过3
        return all(abs(diff) <= 3 for diff in count)

public class Solution {
    public bool CheckAlmostEquivalent(string word1, string word2) {
        int[] count = new int[26];
        
        // 统计频次差值：word1中的字符+1，word2中的字符-1
        foreach (char c in word1) {
            count[c - 'a']++;
        }
        foreach (char c in word2) {
            count[c - 'a']--;
        }
        
        // 检查所有字符的频次差值是否都不超过3
        foreach (int diff in count) {
            if (Math.Abs(diff) > 3) {
                return false;
            }
        }
        
        return true;
    }
}

var checkAlmostEquivalent = function(word1, word2) {
    const count = new Array(26).fill(0);
    
    // 统计频次差值：word1中的字符+1，word2中的字符-1
    for (let c of word1) {
        count[c.charCodeAt(0) - 97]++;
    }
    for (let c of word2) {
        count[c.charCodeAt(0) - 97]--;
    }
    
    // 检查所有字符的频次差值是否都不超过3
    return count.every(diff => Math.abs(diff) <= 3);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)n 是字符串长度，需要遍历两个字符串各一次
空间复杂度O(1)使用固定大小为 26 的数组，空间复杂度为常数

相关题目