0242. Valid Anagram¶
题目信息¶
- 题号:
0242
- 难度:
Easy
- 主题:
字符串、字符频次、哈希表、排序
- 原题:
- 重点:
使用全部字符、每种字符频次完全相同、长度一致、小写英文字母
题目重述¶
给定两个字符串 s 和 t,判断 t 是否是 s 的字母异位词。字母异位词只能重新排列字符顺序,必须恰好使用 s 中的全部字符,因此两个字符串的长度以及每种字符的出现次数都必须完全相同。
s 和 t 的长度均位于 [1, 5 * 10^4],只包含小写英文字母。字符相同但频次不同、频次相同但存在不同字符,或者字符串长度不同,都应返回 false。函数不修改输入字符串。题目的进阶问题询问当输入包含 Unicode 字符时如何调整实现。
自建示例¶
重复字符频次完全一致:
输入:s = "aaccb",t = "cacba"
输出:true
解释:两个字符串都包含两个 a、两个 c 和一个 b,只是排列顺序不同。
字符集合相同但频次不同:
输入: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++ 实现¶
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)。
代码按题目保证的小写字符域做索引,不修改输入字符串;重复字符会分别计数,不会因集合只保留存在性而丢失频次。