Frontend Interview

Appearance

242. 有效的字母异位词 ​

题目链接：https://leetcode.cn/problems/valid-anagram/

代码 ​

ts
/**
 * 242. 有效的字母异位词
 * https://leetcode.cn/problems/valid-anagram/
 */

function isAnagram(s: string, t: string): boolean {
    const map = new Map<string, number>();
    if(s.length !== t.length) return false;
    for (let i = 0; i < s.length; i++) {
        map.set(s[i], (map.get(s[i]) || 0) + 1);
        if (map.get(s[i]) === 0) {
            map.delete(s[i]);
        }
        map.set(t[i], (map.get(t[i]) || 0) - 1);
        if (map.get(t[i]) === 0) {
            map.delete(t[i]);
        }
    }
    return map.size === 0;
}

思路 ​

使用哈希表（Map）来统计字符出现的次数：

  1. 长度判断：如果两个字符串长度不同，直接返回 false
  2. 字符计数：同时遍历两个字符串：
    • 对于字符串 s 中的字符，计数 +1
    • 对于字符串 t 中的字符，计数 -1
    • 当某个字符计数为 0 时，从 Map 中删除该字符
  3. 结果判断：如果最终 Map 为空，说明两个字符串的字符完全匹配，是有效的字母异位词

这种做法只需要遍历一次字符串，同时处理两个字符串的计数，非常高效。

  • 时间复杂度 O(n)，其中 n 为字符串长度
  • 空间复杂度 O(|Σ|)，其中 |Σ| 为字符集大小，最坏情况下需要存储所有不同的字符