有效的字母异位词

🟢 Easy · 🏷️ 哈希表、字符串、排序 · LeetCode#242

📖 题目

判断字符串 t 是否是 s 的字母异位词——两个字符串每个字符出现的次数都相同。

输入	输出
s="anagram", t="nagaram"	true
s="rat", t="car"	false

🆕 新知识

Counter 是 collections 里现成的计数器，统计一个可迭代对象里每个元素出现的次数，比手写哈希表统计省事：

from collections import Counter
Counter("hello")        # Counter({'l': 2, 'h': 1, 'e': 1, 'o': 1})
Counter("hello")['x']   # 0，取不存在的 key 不会报错，直接给 0

手写统计频率时，dict.get(key, default) 能省掉一次 if-else 判断：

count[char] = count.get(char, 0) + 1   # char 不存在就当 0 处理

💡 思路

字母异位词的本质是"字符频率相同"。用 Counter 分别统计两个字符串，比较是否相等即可。

也可以排序后直接比较——异位词排序后结果必然相同，但排序是 O(n log n)，不如统计频率的 O(n)。

💻 代码

方法一：Counter（推荐）

from collections import Counter

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return Counter(s) == Counter(t)

时间复杂度 O(n)，空间复杂度 O(n)。

方法二：手动哈希表

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False

        count = {}
        for char in s:
            count[char] = count.get(char, 0) + 1

        for char in t:
            if char not in count or count[char] == 0:
                return False
            count[char] -= 1

        return True

跟方法一复杂度相同，但 Counter 是 C 实现，实测更快。

方法三：排序

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return sorted(s) == sorted(t)

时间复杂度 O(n log n)，空间复杂度 O(n)——最简单，但不是最优解。