242. 有效的字母异位词

题目

力扣题目

给定两个字符串 s 和 t，判断 t 是否是 s 的字母异位词。字母异位词由相同字母重新排列得到，因此每种字母的出现次数必须完全一致。

示例 1：

输入：s = "anagram", t = "nagaram"
输出：true

示例 2：

输入：s = "rat", t = "car"
输出：false

提示：

• 1 <= s.length, t.length <= 5 × 10^4
• s 和 t 仅包含小写英文字母

考察内容

• 使用固定长度数组统计字符频率
• 字符到数组下标的映射
• 用增减抵消比较两组频率
• 数组零初始化
• 固定字符集带来的 $O(1)$ 额外空间

解题思路

计数数组

题目限定字符串只包含 26 个小写字母，因此无需使用通用哈希表，可以用长度为 26 的数组 count 记录频率：

处理过程：

1. 遍历 s，对应字母的计数加 1；
2. 遍历 t，对应字母的计数减 1；
3. 检查 26 个位置是否全部为 0。

如果所有计数都归零，说明两个字符串中每个字母的出现次数都相同；只要存在非零位置，就不是字母异位词。

以 s = "anagram"、t = "nagaram" 为例，两者均包含：

遍历 s 后得到正计数，再用 t 中的字符逐一抵消，最终所有位置回到 0。

• 时间复杂度：$O(|s| + |t|)$
• 空间复杂度：$O(1)$，计数数组始终只有 26 个位置

排序法

也可以先比较长度，再分别排序两个字符串，最后判断排序结果是否相同。该方法更直观，但时间复杂度为 $O(n\log n)$，且会修改字符串副本。

若字符集扩展为 Unicode，不适合再使用固定的 26 长度数组，可以改用 unordered_map 统计实际字符及其频率。

代码演示

bool isAnagram(const std::string& s, const std::string& t) {
    if (s.size() != t.size()) {
        return false;
    }

    // 花括号确保 26 个位置全部初始化为 0
    std::array<int, 26> count{};

    for (char c : s) {
        ++count[c - 'a'];
    }

    for (char c : t) {
        --count[c - 'a'];
    }

    for (int frequency : count) {
        if (frequency != 0) {
            return false;
        }
    }

    return true;
}

易错点

• 计数数组未初始化：std::array<int, 26> count; 中是未定义值，必须写成 count{} 进行零初始化。
• 字符下标计算错误：小写字母应映射为 c - 'a'，范围是 [0, 25]。
• 只判断出现过哪些字母：字母种类相同但频率不同也不是异位词，例如 "aab" 与 "abb"。
• 忘记长度检查：计数法最终也能发现差异，但提前比较长度可以立即返回并明确表达必要条件。
• 对 t 仍然执行加法：一个字符串加、另一个字符串减，计数才能互相抵消。
• 直接套用 26 长度数组处理其他字符集：题目限定小写字母；Unicode 等更大字符集应使用哈希表。

总结

判断字母异位词等价于判断两个字符串的字符频率表是否相同。利用仅有 26 个小写字母的限制，用固定数组进行增减抵消，可以在线性时间和常数额外空间内完成判断。

相关题目

• 49. 字母异位词分组
• 383. 赎金信
• 438. 找到字符串中所有字母异位词
• 451. 根据字符出现频率排序