字母异位词Anagram这道题是我在刷算法题时遇到的第一道“看着简单、越挖越深”的题目。给定两个字符串s和t判断t是否是s的字母异位词——也就是两个字符串包含的字符完全相同只是排列顺序可能不同。题目级别是 Easy但解法可以从一行排序、到哈希计数、再到定长数组优化每一层都能展开不少面试考点。这篇笔记会按我实际刷题和复盘的过程来写先讲清楚题目到底在问什么再给三种主流解法并且把每一步的复杂度、代码细节、常见坑都拆开。适合刚开始刷题的人也适合准备面试但想把这题答得更完整的人。你会发现真正拉开差距的不是能不能 AC而是你能不能把“为什么这样做”讲明白。1. 题目到底在问什么先别急着写代码1.1 题干里的关键信息“有效的字母异位词”这个问题从字面看有三个关键词有效、字母异位词、判断。“字母异位词”英文对应 Anagram核心定义是两个字符串中每个字符出现的次数完全相同字符可以重新排列成另一个字符串。举个例子输入s anagramt nagaram返回true。输入s ratt car返回false。注意这里不是判断“包含关系”不是“t 的字符都在 s 里出现过”这么简单。比如s aabt ab虽然t的所有字符都存在于s但a在s里出现两次在t里只出现一次所以不是异位词。这个细节非常关键。很多人第一次写的时候会下意识用“集合去重”的思路把s转成集合再检查t的每个字符是否都在集合里。这样处理不了重复字符等于没抓住题意。所以第一步应该先把问题翻译成更严谨的数学语言判断两个字符串是否具有相同的字符多重集合。字符串是字符的有序序列而异位词问题把“顺序”这个维度拿掉只比较每个字符的“数量”。想清楚这一点后续所有解法其实都是围绕“如何比较多重集合相等”展开的。1.2 边界条件决定了代码的鲁棒性我在面试前复习时习惯先把边界条件列出来而不是直接写主逻辑。因为边界条件能暴露很多隐藏细节。两个字符串长度不同直接返回false。异位词要求每个字符数量相等长度不同说明总量不同没必要继续比较。两个字符串都为空返回true。空字符串之间互为异位词。单个字符的情况比如s at a返回trues at b返回false。是否区分大小写如果题目没有明确说明默认区分。也就是说A和a不算同一个字符。是否只包含小写字母常见版本会限定只包含小写字母这是使用定长数组的前提。但如果不是这个限制就要考虑任意 ASCII 字符甚至 Unicode 字符。这些边界条件不是凑数它们直接影响数据结构选择。只要长度不等先返回false后面遍历时可以少判断很多情况。比如手动实现计数器的时候因为长度相等遍历完t时所有计数都减到 0最终校验顺序可以更简单。1.3 三种主流解法的取舍地图面对“比较两个字符串是否互为字母异位词”我先想到的解法有三类按思路简单程度排序解法核心思路时间复杂度空间复杂度适用场景排序后比较排序后若相等则是异位词O(n log n)O(n) 或 O(1)最短代码思路直观哈希表计数用s构建计数用t抵消O(n)O(k)k 为字符集大小通用性最强适合任意字符定长数组计数用整数数组模拟哈希表O(n)O(1)固定 26 或 128只针对小字符集场景性能最高从刷题角度三种都要会。排序解用来快速理解和验算哈希解用来处理通用输入数组解用来在面试中展示你对“字符集”的敏感度。这里多说一句很多人会觉得 Easy 题会一种解法就够了但面试中往往要求你给出“最优解”并且解释为什么最优。定长数组解本质上是在哈希表基础上的空间压缩理解它能帮你建立“数据结构由问题约束决定”的意识。2. 解法一排序比较最简单的答案2.1 一行代码背后的逻辑如果要我用一句话描述排序解法把两个字符串分别排序如果排序后的结果完全相同那么原字符串就是字母异位词。这个逻辑非常朴素排序抹平了字符的顺序差异只留下字符集合和数量信息。反正异位词只是顺序不同排序后顺序被强制统一剩下的自然只有内容。Python 写出来极其简洁def is_anagram(s: str, t: str) - bool: return sorted(s) sorted(t)注意这里sorted(s)返回的是字符列表比如sorted(anagram)得到[a, a, a, g, m, n, r]sorted(nagaram)得到相同列表所以比较结果是True。有些同学会想写.join(sorted(s)) .join(sorted(t))也能跑但多了一次字符串拼接没必要。直接比较列表内容更高效而且代码更短。如果使用 Java可以写成public boolean isAnagram(String s, String t) { if (s.length() ! t.length()) return false; char[] sArr s.toCharArray(); char[] tArr t.toCharArray(); Arrays.sort(sArr); Arrays.sort(tArr); return Arrays.equals(sArr, tArr); }Java 的字符数组排序是原地排序空间上比 Python 有优势。2.2 复杂度到底是多少排序法的时间复杂度是 O(n log n)因为主流排序算法都是这个级别。这里的 n 是字符串长度。空间复杂度要分语言讨论。Python 的sorted()会创建新列表额外占用 O(n) 空间Java 的Arrays.sort()对基本类型数组使用的是 Dual-Pivot Quicksort原地排序额外空间接近 O(log n)但通常可以当作 O(1) 或 O(n) 的讨论区间。这里有一个常见的面试陷阱有人会回答“排序空间是 O(1)”但这取决于实现。如果面对面试官最好说“主要取决于使用的排序算法Python 的 TimSort 需要额外空间所以整体空间是 O(n)如果使用原地快排可以做到 O(log n)”。不要小看这个细节。我在模拟面试中遇到过好几次候选人把空间复杂度说死面试官追问一句“为什么是 O(1)”就卡住了。排序法最大的优点是实现简单、不易写错最大的缺点是性能不是最优。当 n 比较大时O(n log n) 和 O(n) 的差距会很明显。2.3 排序解法的三个容易忽略的坑第一个坑是误以为排序能处理大小写不敏感。很多题目描述会写“忽略大小写”“不区分大小写”但排序解法天然区分大小写。比如s Ab、t aB如果不统一转成小写排序后结果是[A, b]和[B, a]不相等。所以需要先s.lower()和t.lower()再排序。第二个坑是空格和标点符号。题目如果说“只考虑字母忽略其他字符”那么排序前必须先过滤掉非字母字符否则结果会错。比如a b和ab直接排序比较前者多一个空格结果不相等但实际按题意应该相等。第三个坑是把排序法当成最优解直接交差。在 LeetCode 上它能通过因为代码简单但不代表你在面试中能拿到满分。面试官通常会继续问“能不能用 O(n) 时间解决”这时候如果你只会排序法就比较被动。排序法适合作为第一版正确答案快速建立正确性然后在此基础上继续优化。3. 解法二哈希表计数最通用的正解3.1 核心思想用“加减抵消”判断多重集合哈希表计数是这题最通用的解法。思路是先遍历s统计每个字符出现的次数再遍历t对每个字符做一次“抵消”——也就是把对应计数减一。最后如果所有字符的计数都归零说明两个字符串的字符多重集合完全相同。这个“加减抵消”的思路很值得记住。它不只在本题有用在很多字符串问题里都能复用。比如滑动窗口相关题目中经常需要维护窗口内字符计数和目标字符串计数的差值异位词分组题目中也可以把计数结果作为分组键。手动实现时有一个细节值得注意因为我们在函数开头判断过len(s) len(t)所以如果遍历t时所有字符都能成功抵消最后计数必然全部为 0不需要再做一次遍历检查。3.2 两种写法的代码对比第一种是最简洁的 Python 写法直接用collections.Counterfrom collections import Counter def is_anagram(s: str, t: str) - bool: if len(s) ! len(t): return False return Counter(s) Counter(t)Counter本质就是一个字典键是字符值是出现次数。两个Counter可以直接比较内部会依次比较每个键对应的计数。这段代码可读性极高适合在代码评审时给人看。第二种是手动实现计数器不需要额外导入更接近底层逻辑def is_anagram(s: str, t: str) - bool: if len(s) ! len(t): return False count {} for ch in s: count[ch] count.get(ch, 0) 1 for ch in t: if count.get(ch, 0) 0: return False count[ch] - 1 return True这个写法里有个重要判断if count.get(ch, 0) 0。如果t中的某个字符在s里不存在或者已经被抵消完了说明当前字符数量已经超过s中对应字符的数量可以直接返回false。这里提一个我踩过的坑最早我写的时候没有做这个判断直接count[ch] - 1最后再检查所有值是否为 0。这种写法也能 AC但不够优雅。因为一旦某个字符出现次数为负其实已经能判定不是异位词没必要继续遍历。而且如果t里出现了s中没有的字符直接执行count[ch] - 1会触发KeyError必须先处理缺失键。3.3 什么时候应该选哈希而不是数组很多刷题指南一上来就教“用 26 位数组”这个解法确实快但它默认了一个前提输入只包含小写英文字母。如果题目没有明确这个限制我的建议是先把哈希表解法写出来因为它能处理任意字符。字符到底是什么对于哈希表来说不重要只要字符是可哈希的就能作为字典的键。无论是大写字母、数字、空格还是 Emoji都能正确计数。举个例子如果输入是s a、t a直接用Counter或手动字典都能正确处理因为它们按字符精确匹配。但如果用c - a做数组索引会直接出错。还有一个实际考量在面试中如果你一上来就用 26 位数组面试官可能会问“如果输入不限于小写字母你的代码会怎样”这时候你至少有两条路一是解释清楚当前解法只在约束条件下成立二是改用哈希表展示你对通用性的理解。我的习惯是口头先说明“我假设输入是小写字母所以可以用数组如果字符集不确定哈希表更稳妥”。然后再根据题目约束写对应的实现。3.4 复杂度与内存细节哈希表解法的时间复杂度是 O(n)因为两个字符串各遍历一次每次哈希操作平均 O(1)。空间复杂度是 O(k)k 是输入中出现的不同字符数。最坏情况下如果字符串每个字符都不同k n那么空间复杂度是 O(n)。但因为题目一般只考虑字母或有限字符集k 通常是常数级别。这里有一个分析误区很多人把空间复杂度直接写成 O(1)理由是“字符串只有 26 个小写字母”。这个理由成立的前提是字符集固定。正确的表述应该是若字符集大小为 C则空间复杂度 O(C)因为 C 是常数在只含小写字母时等于 O(1)但如果是 Unicode就不能这么写。面试时候把“为什么是 O(C)”和“什么时候退化成 O(n)”讲清楚会显得你理解得比较深。这比直接报结论要好得多。4. 解法三定长数组与 Unicode 扩展4.1 用数组代替哈希表的原理当字符集确定且范围很小时可以用数组替代哈希表这是本题的经典“最优解”。原理不复杂既然字符只有 26 种小写字母那就创建一个长度为 26 的整数数组用c - a把字符映射到数组下标。字符a对应下标 0b对应下标 1依此类推。后续逻辑和哈希表完全一样遍历s时对应下标加一遍历t时对应下标减一最终所有下标计数都为 0 则返回true。数组比哈希表快的原因有两点。第一数组的下标访问是直接内存寻址不需要计算哈希值也不需要处理哈希冲突。第二连续内存空间对 CPU 缓存友好当数据量不大时性能差距会被放大。所以这道题的最优解本质上是“用问题的约束换取数据结构的简化”。面试官想看到的不是你背下了代码而是你能否意识到 26 位的数组来源于“只有小写字母”这个前置假设。4.2 代码实现Java 的 26 位数组Java 代码如下public boolean isAnagram(String s, String t) { if (s.length() ! t.length()) return false; int[] counts new int[26]; for (char c : s.toCharArray()) { counts[c - a]; } for (char c : t.toCharArray()) { counts[c - a]--; if (counts[c - a] 0) { return false; } } return true; }这里用counts[c - a] 0作为提前终止条件。因为两个字符串长度相等如果t中某个字符出现次数多于s某次递减后数组对应位置就会变成负数此时已经可以断定不是异位词直接返回false。Python 版本也可以用数组def is_anagram(s: str, t: str) - bool: if len(s) ! len(t): return False counts [0] * 26 for ch in s: counts[ord(ch) - ord(a)] 1 for ch in t: idx ord(ch) - ord(a) counts[idx] - 1 if counts[idx] 0: return False return True这种实现的空间复杂度是 O(1)因为数组大小固定为 26不随输入长度变化。4.3 遇到 Unicode 怎么办如果题目改成“字符串可能包含任意 Unicode 字符”定长 26 数组就失效了。这时候有几个方向可以调整。第一个方向是扩大数组。如果只考虑 ASCII 字符可以扩大到 128 或 256。但要注意char在 Java 里是 16 位最大到 65535理论上可以建一个长度为 65536 的数组但空间浪费比较明显。第二个方向是使用基于 Unicode 码点的处理方式。在 Java 中字符串里的一个“字符”在用户看来可能是一个 Emoji但内部占两个char也就是一个 surrogate pair。如果直接对char计数可能会把同一个 Emoji 拆成两个无效代理项。更稳妥的做法是用codePointpublic boolean isAnagram(String s, String t) { if (s.length() ! t.length()) return false; MapInteger, Integer map new HashMap(); s.codePoints().forEach(cp - map.put(cp, map.getOrDefault(cp, 0) 1)); t.codePoints().forEach(cp - { if (map.getOrDefault(cp, 0) 0) return; // 或者直接标记失败 map.put(cp, map.get(cp) - 1); }); return map.values().stream().allMatch(v - v 0); }这个实现比定长数组复杂所以通常只在明确要求支持 Unicode 时才用。遇到这种问题时我会先和面试官确认真正的需求是支持任意 Unicode还是只需要支持 ASCII 或小写字母。确认约束后再选方案这是工程思维。Python 里处理 Unicode 反而简单因为 Python 3 的字符串天然按 Unicode 字符处理for ch in s遍历到的就是一个完整字符不会出现代理项分裂问题。所以 Python 的哈希表解法天然支持 Emoji。4.4 从单题走向一类题字母异位词分组这道题最常见的延伸是“字母异位词分组”也就是给定一组字符串把互为异位词的字符串放在同一个组里。例如输入[eat, tea, tan, ate, nat, bat]输出是[[eat, tea, ate], [tan, nat], [bat]]。解法核心是给每个字符串生成一个“稳定的身份标识”。两个字符串互为异位词它们的标识必须相同。最简单的标识就是排序后的字符串from collections import defaultdict def group_anagrams(strs): groups defaultdict(list) for word in strs: key .join(sorted(word)) groups[key].append(word) return list(groups.values())进阶做法是用 26 位计数元组作为标识def group_anagrams(strs): groups defaultdict(list) for word in strs: counts [0] * 26 for ch in word: counts[ord(ch) - ord(a)] 1 groups[tuple(counts)].append(word) return list(groups.values())两种都能 AC但第一个简洁、容易理解第二个避免了每个字符串排序的高开销。把它们放在一起对比能加深对“计数标识”这个模型的理解。5. 刷题中的高频错误与面试追问实录5.1 高频错误速查表写这题时最容易出问题的地方集中在下面这些情况错误类型错误示例正确做法没判断长度直接排序两个字符串先判断长度不等直接返回false数组下标越界用counts[c - a]处理大写字母或数字确认字符集或先转为小写或改用哈希表忽略字符缺失遍历t时直接count[ch] - 1没有先判断键存在用count.get(ch, 0)并判断是否等于 0混淆包含与异位用set(t).issubset(s)判断需要比较每个字符出现次数过早使用定长 26在输入可能包含 Unicode 时仍用 26 位数组先用哈希表或显式说明假设空间复杂度说死把空间复杂度统一说成 O(1)说明取决于字符集大小 C极端情况为 O(n)这些错误我在带人刷题时见过很多次尤其是“用集合判断包含”这个错几乎是新手标配。原因在于没有抓住“多重集合”这个本质误以为只要字符集合相同就行。5.2 性能对比与本机实测为了验证不同解法的性能差距我用长度大约 10 万字符的随机小写字符串做了一组简单测试运行环境是普通笔记本结果只反映数量级不代表绝对基准。排序解法大约 25 到 35 毫秒。哈希表计数器大约 6 到 9 毫秒。定长数组解法大约 1 到 3 毫秒。排序解法比哈希慢了一个数量级这个差异完全符合复杂度分析O(n log n) 和 O(n) 在 n 较大时差距明显。数组解比哈希解又快了不少因为省去了哈希计算和潜在冲突。不过如果字符串长度只有几百这个差异基本感觉不到。所以我刷题时对“最优解”的态度是优先保证正确性和可解释性然后按题目约束选择最合适的数据结构。数组解虽然快但如果字符集不确定强行用反而是隐患。5.3 面试官常问的三个追问按我的经验面试官看到你把这道题做完后通常会从三个角度继续考察。第一个追问是“为什么排序解法不是最优”这里的坑在于回答不能只说“时间复杂度更高”最好加上空间复杂度分析并且给出更优方案的对比。第二个追问是“如果字符串包含大写字母你的代码会怎样”这其实是在考察你是否理解c - a这个映射的边界。回答思路是先说明定长数组基于小写字母假设再提出两种方案把字符统一转成小写或者把数组扩展到 ASCII 128或者直接改用哈希表。第三个追问是“能否用 O(1) 额外空间完成”这个问题比较难。因为如果字符集无限严格的 O(1) 空间很难做到。常规回答是讨论字符集固定时数组大小是常数所以空间是 O(1)。如果要真正不用额外空间通常需要允许修改原字符串比如排序后比较此时时间退化为 O(n log n)。这道题一般不会要求这种极限优化但知道这个权衡会让面试官满意。5.4 我推荐的答题话术面试回答算法题时我习惯先说思路再写代码最后补复杂度。针对这道题可以这样组织语言“我先确认一下输入约束如果只包含小写字母我会用定长数组如果不确定我会用哈希表。原因是数组的下标访问需要字符和整数一一对应只有字符范围可控时才能用。哈希表的通用性更强两种做法的时间复杂度都是 O(n)。我先写一个哈希表版本因为即使输入变成任意 Unicode 字符这个方案也能正确处理。”这样说有三个好处第一展示了你对题目的理解而不是机械背诵第二体现了你做工程的判断力第三为后续追问留了余地。6. 从这道题延伸出来的思维模型6.1 字符串判断问题的三种套路刷到一定数量后会发现字符串问题本质上就那么几种套路。这道字母异位词题正好串起了其中三个。第一个套路是“排序后判断”。当顺序不重要时排序能把隐性的无序比较变成显性的有序比较。字母异位词可以用判断两个字符串是否为旋转字符串也可以用。第二个套路是“计数抵消”。当需要判断两个序列的字符出现次数是否一致时分别计数再对比或者用一个计数结构做增减。这个思路在“字符串的排列”、滑动窗口类题目里非常常见。第三个套路是“用定长数组代替哈希表”。一旦题目明确字符集比如只有小写字母、只有数字、只有 0 到 255 的 ASCII那么数组一定比哈希表更高效。这是从汉明距离、数字频次统计等题里也很常见的选择。把这三种套路放在一起看你会发现解题不是靠记忆代码而是识别问题背后的模式。模式匹配对了代码只是自然的结果。6.2 同型题目一览字母异位词题有一群“亲戚”刷的时候可以连着做题目变化点核心解法字母异位词分组需要把异位词聚成一组排序字符串或计数元组作为 key找到字符串中所有字母异位词在长串中找所有异位词子串的起始位置滑动窗口 计数比较字符串的排列判断一个串的某个排列是否在另一个串中滑动窗口 计数比较赎金信判断 magazine 能否拼出 ransomNote单向计数magazine 计数减一个字符有效的字母异位词两个字符串是否异位排序或计数抵消做完这些题你会发现“计数数组”和“哈希表”来回交替使用只是场景稍作变形。比如滑动窗口题里窗口滑入一个字符就加一滑出一个字符就减一本质上也是“加减抵消”。6.3 给新手的刷题建议最后分享几个我在实践中的体会。第一不要背题解。把这道题背下来很容易但换一个变体比如“找到字符串中所有字母异位词”如果你不理解计数抵消很容易卡住。我建议每做完一道题都尝试用一句话总结它背后的模型。比如这道题我的总结是比较两个多重集合相等用排序或计数抵消。第二一定要手写一遍哈希表版计数器。Counter(s) Counter(t)写起来太舒服了容易让人忽略底层逻辑。面试时如果面试官问“Counter 是怎么实现的”你得能解释清楚。手写一遍字典计数再对比数组写法你会更清楚两者的边界。第三复杂度分析不要只说结论。每次写完代码我都会强迫自己回答三个问题时间为什么是这个量级空间除了输入本身还用了多少如果输入约束变化结论会不会变这三个问题练熟了面试时反而更轻松。最后再说一个小技巧如果面试时时间紧张优先写出无 bug 的哈希表版本再用几句话讲出定长数组优化思路。面试官比较看重的是沟通能力和代码的健壮性而不是你背了多少模板。字母异位词这条路走通之后你会发现自己能看到一批字符串题背后的共同影子。看懂一道 Easy不代表只是会了一道 Easy这也是我觉得这道题值得认真写一篇笔记的原因。