0242.有效的字母异位词
难度：🟢 简单
标签：哈希表、字符串、排序
题目描述
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意： 若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true
示例 2:
输入: s = "rat", t = "car"
输出: false
解题思路
核心思想
本题的核心是判断两个字符串是否包含完全相同的字符，并且每个字符出现的频率也完全相同。解决这个问题的关键在于如何高效地统计和比较两个字符串的字符频率。
思路选择
哈希表（字符频率计数器） 是解决此问题的标准最优思路。
既然是字母异位词，它们的长度必然相等，这是首要的判断条件。
我们可以用一个哈希表或一个定长数组来记录第一个字符串
s中每个字符的出现次数。然后，我们遍历第二个字符串
t，对于t中的每个字符，我们就在哈希表中将对应字符的计数减一。如果在遍历
t的过程中，发现某个字符在哈希表中不存在，或者其计数已经为 0，那么t必然不是s的字母异位词。如果
t遍历完毕后没有出现上述情况，则说明两者是字母异位词。
由于题目中可能只涉及小写字母，使用一个长度为 26 的数组作为频率计数器，会比通用的哈希表效率更高。
关键步骤
检查长度：如果
s和t的长度不相等，直接返回false。初始化计数器：创建一个长度为 26 的数组
charCount，并全部填充为 0。统计
s：遍历字符串s，将每个字符出现的频率记录在charCount数组中。核销
t：遍历字符串t，将charCount中对应字符的计数减一。检查结果：在核销
t的过程中，如果发现任何一个字符的计数变为负数，说明t中该字符的数量多于s，直接返回false。如果遍历完成，说明两个字符串是字母异位词。
代码实现
/**
* @param {string} s
* @param {string} t
* @return {boolean}
*/
var isAnagram = function (s, t) {
if (s.length !== t.length) return false;
// 使用 Object 模拟 Map
let map = {}; // 优化为 let map = new Map() 或定长数组更好
// 统计 s 中字符频率
for (let i = 0; i < s.length; i++) {
if (map[s[i]]) {
map[s[i]]++;
} else {
map[s[i]] = 1;
}
}
// 核销 t 中字符
for (let i = 0; i < t.length; i++) {
// 如果 t 中的字符在 map 中不存在，或数量已为0，则不匹配
if (!map[t[i]]) { // !map[t[i]] 在 map[t[i]]为0时也会为true
return false;
}
map[t[i]]--;
}
return true;
};
复杂度分析
时间复杂度：O(n) 其中 n 是字符串
s的长度。我们需要遍历两个字符串一次，以及遍历一次定长的计数器数组。空间复杂度：O(Σ) 其中 Σ 是字符集的大小。对于小写英文字母，Σ 为 26，这是一个常数，因此空间复杂度可以认为是 O(1)。
相关题目
总结
本题是哈希表应用的入门经典，旨在考察对字符频率的统计与比较。通过使用一个数组作为频率计数器，可以得到一个非常简洁且高效的解决方案，这是处理字符相关问题时常用的技巧。