004 · Valid Anagram
My First Thoughts
这道题开始考察字符串。
一开始会觉得这个要求有点奇怪。实际应用里如果是密码验证，通常应该要求两个字符串一模一样；但这里不是。这里要求的是 t 是不是 s 的 anagram，也就是顺序可以不同，但用到的字符和每个字符出现的次数必须一样。
所以问题不是比较两个字符串是否完全相等，而是比较它们的“字符库存”是否一样。
想知道 t 是不是 s 的 anagram，就得先知道 s 里有什么。不过第一反应不一定是分别遍历 s 和 t，算出两边所有字母的出现次数。
更直觉的想法是：直接看 t。
逐个遍历 t 里的字符，让它去 s 里找对应字符。如果这个字符在 s 中，就从 s 里移除它。这样 t 每使用一个字符，s 就少一个字符。等 t 全部遍历完，如果 s 也刚好被消耗完，就说明两个字符串是 anagram。
大概像这样：
def is_anagram(s: str, t: str) -> bool:
for char in t:
if char not in s:
return False
s = remove_one_char(s, char)
return s == ""这个思路的核心是对的：anagram 本质上就是字符库存能不能刚好互相抵消。
另外也可以想到排序。因为顺序不重要，那就把两个字符串都排序，然后判断排序后的结果是否相同：
def is_anagram(s: str, t: str) -> bool:
return sorted(s) == sorted(t)这个方法能做，而且代码很短。但排序并不是唯一选择。
Why That Is Not Enough
“逐步减少字符串”的想法有一个问题：从字符串里查找并移除字符，开销并不是 \(O(1)\)。
在 Python 里，字符串是不可变的。每次移除一个字符，都不是在原字符串上直接删掉，而是重新构造一个新字符串。再加上 char in s 本身也可能需要扫描字符串，所以如果 t 的每个字符都去 s 里找一次、删一次，整体很容易变成 \(O(n^2)\)。
也就是说，这个想法在逻辑上接近答案，但数据结构不合适。
真正需要维护的不是一个可以被删除的字符串，而是一个可以被减少的字符计数表。
例如 s = "anagram"，可以先记录成：
a: 3
n: 1
g: 1
r: 1
m: 1然后遍历 t，每看到一个字符，就把对应计数减一。这就相当于让 t 去消耗 s 的字符库存，但每次消耗只需要更新一个数字。
排序法也可以通过这题，但排序做了额外工作：它把字符放进了一个全局顺序里。题目只关心每个字符出现几次，并不关心字符排成什么顺序。
另外，两个字符串长度不同的时候，一定不可能是 anagram，可以先提前返回 False。
Final Idea
用一个 hash map 记录字符计数。
先遍历 s，每看到一个字符，就把它的计数加一。
再遍历 t，每看到一个字符，就把它的计数减一。如果某个字符不在 map 里，或者已经没有可抵消的次数，就说明 t 多用了一个 s 里没有的字符，直接返回 False。
遍历结束后，所有字符都刚好抵消完，就返回 True。
Why It Works
anagram 的核心条件不是“字符集合相同”，而是“每个字符的出现次数相同”。
第一个循环把 s 的字符频率存下来。第二个循环用 t 的字符逐个抵消这些频率。
如果 t 中某个字符无法抵消，说明两个字符串的频率不同。反过来，如果长度相同，并且 t 的每个字符都能成功抵消，那么所有计数最终都会归零，两个字符串就是 anagram。
Code
def is_anagram(s: str, t: str) -> bool:
if len(s) != len(t):
return False
counts = {}
for char in s:
counts[char] = counts.get(char, 0) + 1
for char in t:
if char not in counts or counts[char] == 0:
return False
counts[char] -= 1
return TrueComplexity
| Time | \(O(n)\) — 两个字符串各遍历一次 |
| Space | \(O(1)\) — 只有 26 个小写英文字母，字符种类数固定 |
Takeaway
当题目说“顺序不重要，但出现次数重要”时，优先想到 frequency count。排序可以把相同字符排到一起，但如果目标只是比较次数，直接用 hash map 计数通常更贴近问题本身。
← Quiz