0242. Valid Anagram =================== 题目信息 -------- :题号: 0242 :难度: Easy :主题: 字符串、字符频次、哈希表、排序 :原题: `LeetCode 0242 `_ :重点: 使用全部字符、每种字符频次完全相同、长度一致、小写英文字母 题目重述 -------- 给定两个字符串 ``s`` 和 ``t``,判断 ``t`` 是否是 ``s`` 的字母异位词。字母异位词只能重新排列字符顺序,必须恰好使用 ``s`` 中的全部字符,因此两个字符串的长度以及每种字符的出现次数都必须完全相同。 ``s`` 和 ``t`` 的长度均位于 ``[1, 5 * 10^4]``,只包含小写英文字母。字符相同但频次不同、频次相同但存在不同字符,或者字符串长度不同,都应返回 ``false``。函数不修改输入字符串。题目的进阶问题询问当输入包含 Unicode 字符时如何调整实现。 自建示例 -------- 重复字符频次完全一致: .. code-block:: text 输入:s = "aaccb",t = "cacba" 输出:true 解释:两个字符串都包含两个 a、两个 c 和一个 b,只是排列顺序不同。 字符集合相同但频次不同: .. code-block:: text 输入:s = "abbc",t = "abcc" 输出:false 解释:s 中 b 出现两次而 c 出现一次,t 中这两个频次相反,因此不是字母异位词。 频次守恒 -------- 字母异位词只允许重排,不允许增加、删除或替换字符。因此先比较长度;长度相同后, 扫描 ``s`` 对对应字母计数加一,扫描 ``t`` 减一。若最终所有 26 个计数都为 0, 两串对每个字符的出现次数完全相同;只要某个计数不为 0,就存在字符频次差异。 可以在第二次扫描时一旦发现某个计数变成负数就返回假,但最后统一检查更容易直接对应频次等式。 本题字符域固定为小写 ``a`` 到 ``z``,数组下标比哈希表更直接;若题目改为 Unicode,才需要按完整字符单位选择其他映射。 正确性说明 ---------- 处理完两个字符串后,``count[c]`` 等于字符 ``c`` 在 ``s`` 中的出现次数减去在 ``t`` 中的出现次数。 若所有计数为 0,两边每种字符数量一致,可以把 ``s`` 的字符逐个重排成 ``t``;若有非零计数, 至少一种字符数量不同,任何重排都无法得到 ``t``。长度检查覆盖了总字符数不相等的情况。 C++ 实现 -------- .. code-block:: cpp class Solution { public: bool isAnagram(const std::string& s, const std::string& t) { if (s.size() != t.size()) return false; int count[26] = {}; for (char ch : s) ++count[ch - 'a']; for (char ch : t) --count[ch - 'a']; for (int value : count) { if (value != 0) return false; } return true; } }; 代码分析 -------- 两次扫描时间复杂度为 ``O(n)``,频次数组固定为 26 个整数,额外空间为 ``O(1)``。 代码按题目保证的小写字符域做索引,不修改输入字符串;重复字符会分别计数,不会因集合只保留存在性而丢失频次。