有效的字母异位词

题目描述

给定两个字符串 s 和 t，编写一个函数来判断 t 是否是 s 的字母异位词。

字母异位词定义：两个单词包含的字母种类和每个字母出现的次数完全相同，只是字母的排列顺序不同。

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

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

进阶：如果输入字符串包含 Unicode 字符（而不仅仅是小写字母），你该如何调整？

解题过程循序渐进讲解

第一步：理解问题本质

字母异位词的核心在于字母频次完全相同。
因此，我们需要比较两个字符串中：

1. 包含的字符集合是否相同
2. 每个字符出现的次数是否相等

第二步：初步思路

最直接的方法：

1. 统计 s 中每个字符出现的次数
2. 统计 t 中每个字符出现的次数
3. 比较两个统计结果是否完全一致

第三步：选择数据结构存储频次

哈希表（Hash Table）是最自然的选择：

• 键（Key）：字符
• 值（Value）：该字符出现的次数

第四步：具体步骤（以小写字母为例）

方法一：使用两个哈希表

1. 创建两个哈希表（如字典），分别记为 count_s 和 count_t。
2. 遍历字符串 s，对每个字符 c：
   • 如果 c 不在 count_s 中，则 count_s[c] = 1
   • 如果 c 已在 count_s 中，则 count_s[c] += 1
3. 同样遍历 t，填充 count_t。
4. 比较 count_s 和 count_t 是否完全相等。

时间复杂度：O(n)，其中 n 为字符串长度
空间复杂度：O(1)（字符集大小固定，如小写字母为 26）

方法二：使用一个哈希表（优化空间）

1. 创建一个哈希表 count，只统计 s 的字符频次。
2. 遍历字符串 s，对每个字符 c，执行 count[c] += 1。
3. 遍历字符串 t，对每个字符 c：
   • 如果 c 不在 count 中，直接返回 false（t 包含 s 中没有的字符）。
   • 如果 c 在 count 中，则将 count[c] -= 1。
4. 遍历完成后，检查 count 中所有值是否均为 0。
   • 如果全是 0，说明 s 和 t 字符频次相同。
   • 如果有值不为 0，说明频次不一致。

示例推导（s = "anagram", t = "nagaram"）：

• 统计 s：a→3, n→1, g→1, r→1, m→1
• 遍历 t：
  • n: a→3, n→0, g→1, r→1, m→1
  • a: a→2, n→0, g→1, r→1, m→1
  • g: a→2, n→0, g→0, r→1, m→1
  • a: a→1, n→0, g→0, r→1, m→1
  • r: a→1, n→0, g→0, r→0, m→1
  • a: a→0, n→0, g→0, r→0, m→1
  • m: a→0, n→0, g→0, r→0, m→0
• 所有值均为 0 → 是字母异位词

第五步：代码实现（Python示例）

def isAnagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    
    count = {}
    for c in s:
        count[c] = count.get(c, 0) + 1
    for c in t:
        if c not in count:
            return False
        count[c] -= 1
        if count[c] == 0:
            del count[c]  # 可选，减少最后检查的键数量
    return len(count) == 0

解释：

• 先检查长度，长度不同可直接返回 false。
• count.get(c, 0) 返回键 c 对应的值，如果键不存在则返回 0。
• 遍历 t 时，如果某个字符不在 count 中，直接返回 false。
• 最后检查 count 是否为空（所有频次抵消干净）。

第六步：进阶情况（Unicode字符）

当字符范围很大（Unicode）时，上述哈希表方法依然有效：

• 哈希表会自动适应字符种类，空间复杂度为 O(k)，k 是字符种类数（≤ 字符串长度）。
• 算法步骤完全相同，因为哈希表可处理任意可哈希的字符。

第七步：替代方法（适用于限定字符集）

如果题目说明字符只包含小写字母（如 26 个字母），可以使用固定大小的数组代替哈希表：

def isAnagram(s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    counter = [0] * 26
    for c in s:
        counter[ord(c) - ord('a')] += 1
    for c in t:
        idx = ord(c) - ord('a')
        if counter[idx] == 0:
            return False
        counter[idx] -= 1
    return True

• 数组索引 0~25 代表 'a'~'z'。
• ord(c) - ord('a') 将字符映射到索引。

第八步：其他变体思路

• 排序法：将两个字符串排序后比较是否相等。时间复杂度 O(n log n)，空间复杂度取决于排序实现。
• Python 一行写法：return sorted(s) == sorted(t)，简洁但效率较低。

总结

核心：字母异位词的本质是字符频次相同。
推荐方法：使用单个哈希表统计频次，一边加一边减，最后检查是否平衡。
优势：时间 O(n)，空间 O(k)（k 为字符种类数），适用于任意字符集。