1. 题目本身是个什么意思先聊个题外话。不管是校招还是社招只要面试官想考察候选人对“字符串处理”和“基础数据结构”的掌握程度十个里面有八个会从这类“看起来很简单”的题开始。有效的字母异位词就是这么一道题LeetCode 上编号242难度标的是Easy但在实际面试中它的区分度一点不比 Medium 低。题目原文大概是这样给定两个字符串s和t写一个函数来判断t是否是s的字母异位词。所谓“字母异位词”指的就是两个字符串里出现的字母种类相同、每种字母出现的次数也相同但字母的排列顺序可以不同。比如s anagramt nagaram这两个就是字母异位词因为a出现 3 次、n出现 1 次、g出现 1 次、r出现 1 次、m出现 1 次两个字符串的字符频率表完全一样。反过来如果s ratt car虽然都是三个字母但r、a、t和c、a、r的组成不一样所以不是。这道题解决的痛点很直接在文本处理、拼写检查、关键词匹配这些场景里我们经常要判断两段文本在“字符组成”上是不是等价的而不关心它们的排列顺序。比如垃圾邮件过滤中检测变体词、搜索引擎处理同字母异序词、甚至某些加密算法里的字母重排底层都会用到这套逻辑。这道题适合谁来刷我建议三类人必须吃透它准备面试的候选人尤其是面后端、客户端、算法岗的这道题几乎是“必刷清单”里的钉子户刚学数据结构和算法、对“哈希表”和“数组计数”还没有手感的新手拿它入门非常合适写业务代码写到麻木、想找回一点算法基本功的工程师用它热热身也再好不过。下面我按自己的刷题习惯把这道题从“粗解”到“最优解”再到“面试官追问”的完整链路拆开讲一遍。2. 初看题目的第一反应排序比较法我第一次看到这道题的时候脑子里冒出来的方案其实不是哈希表而是排序。原因很简单如果两个字符串互为字母异位词那么把它们各自按字符排序之后得到的结果一定完全相同。反过来说如果两个排序后的字符串不相等那它们必然不是字母异位词。这个思路用代码写起来极其直白def is_anagram(s: str, t: str) - bool: return sorted(s) sorted(t)没错Python 里一行就搞定了。Java 版本也就是多几行的事public boolean isAnagram(String s, String t) { if (s.length() ! t.length()) { return false; } char[] sArray s.toCharArray(); char[] tArray t.toCharArray(); Arrays.sort(sArray); Arrays.sort(tArray); return Arrays.equals(sArray, tArray); }2.1 排序法的时间与空间复杂度这里必须把复杂度账算清楚。排序本身的时间复杂度是O(n log n)其中n是字符串的长度。两个字符串各排一次最坏情况下就是O(n log n)严格说系数是 2但数量级不变。额外空间方面Java 的toCharArray()会产生两个字符数组所以是O(n)的辅助空间Python 的sorted()也会生成新的列表同理。2.2 排序法的优势与劣势这个方案的优点是“正确性一目了然”。对于面试开场来说能 30 秒内写出来并且逻辑完全自洽至少说明你具备“先有可行解、再做优化”的工程思维。面试官不会因为你先写了暴力解就给你扣分反而会看你后续能不能主动优化。但缺点同样明显。O(n log n)的时间复杂度在字符串很长的时候不够看。假设两个字符串长度为 10 万排序就要做几十万次比较操作而如果换成哈希计数只需要线性扫描一遍差距一下就拉开了。另外排序用了额外空间这在某些要求“原地比较”或“极低空间占用”的场景里也是个减分项。所以排序法在我的笔记里定位是“兜底方案”和“对照参照物”。真正面试时的主答案建议用下面这种更正统的思路。3. 正统解法用哈希表统计字符频率哈希表或者更具体地说字符到次数的映射是解决字母异位词问题最自然的数据结构。核心逻辑是先遍历字符串s把每个字符出现的次数累加到哈希表里再遍历字符串t每遇到一个字符就从哈希表里减去一次。如果最终哈希表里所有键对应的值都是 0说明两个字符串的字符频次完全匹配。这个思路其实特别像生活中对账的过程——左边记一笔收入右边记一笔支出最后看账平不平。3.1 Python 的 Counter 写法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做相等比较时会比较每个字符的计数是否完全一致。这个写法在力扣上能跑出非常不错的成绩而且代码可读性极佳。但要注意Counter在工程上很好用面试手写的时候最好不要直接甩出来否则面试官看不出你对底层原理的掌握程度。我的建议是口头上说“可以用哈希表计数”然后手写原始字典实现。3.2 手写字典实现用最朴素的字典手动维护计数def is_anagram(s: str, t: str) - bool: if len(s) ! len(t): return False counter {} for ch in s: counter[ch] counter.get(ch, 0) 1 for ch in t: if ch not in counter: return False counter[ch] - 1 if counter[ch] 0: return False return True这里有个小细节值得展开讲为什么可以在循环中途提前return False因为在已经保证len(s) len(t)的前提下如果遍历t时某个字符的计数跳到了负数说明t里这个字符出现的次数已经超过了s中该字符的总量。既然总长度相等某个字符多出来了那必然有另一个字符会少掉所以可以立即判定不是字母异位词。这个“提前剪枝”的操作能让代码在大多数不匹配的用例上少跑很多无谓的循环。3.3 哈希表解法的时间与空间复杂度时间复杂度是O(n)因为两个循环都是线性的每个字符最多被处理常数次。空间复杂度是O(1)还是O(n)这取决于你怎么定义。严格来说哈希表存储了s中所有不同的字符最多有n个不同字符所以空间复杂度是O(n)。但是如果题目限定输入只包含小写字母LeetCode 原题是s和t仅包含小写字母那么不同字符最多 26 个哈希表的规模就是常数级可以理解为O(1)。这里我建议面试时主动和面试官确认“如果输入只包含小写英文字母那我们可以进一步优化为固定大小的数组计数。”这句话一说出来面试官会立刻知道你对复杂度边界有清晰认知。延续这个话题就进入了下一节要讲的“最优解”。4. 最优解用长度为 26 的数组做计数器当题目明确说明字符串只包含小写字母时我们可以用数组来代替哈希表。思路是申请一个长度为 26 的整型数组count下标0对应a下标1对应b以此类推。遍历s时对应位置加一遍历t时对应位置减一。最后看数组里是否所有元素都为 0。4.1 如何优雅地把字符映射到数组下标这个映射是整道题里最核心的“常识点”ord(ch) - ord(a)。在 Python 里def is_anagram(s: str, t: str) - bool: if len(s) ! len(t): return False count [0] * 26 for ch in s: count[ord(ch) - ord(a)] 1 for ch in t: count[ord(ch) - ord(a)] - 1 return all(x 0 for x in count)Java 版本public boolean isAnagram(String s, String t) { if (s.length() ! t.length()) { return false; } int[] count new int[26]; for (int i 0; i s.length(); i) { count[s.charAt(i) - a]; } for (int i 0; i t.length(); i) { count[t.charAt(i) - a]--; } for (int value : count) { if (value ! 0) { return false; } } return true; }这里有一个 Java 特有的坑s.charAt(i) - a得到的结果类型是int而不是char因为 Java 中字符相减会自动提升为整数。新手容易在这里犯迷糊写成s.charAt(i) - 97虽然也能跑但可读性差了一些建议还是用a字符常量参与运算代码一看就懂还不会因为魔法数字引发 review 吐槽。4.2 为什么说这是“最优解”时间复杂度仍然只有O(n)两个字符串各遍历一次再加上最后检查数组的O(26)也就是常数项整体还是O(n)。空间复杂度固定长度的数组O(1)不会随着输入字符串变长而增加。实现逻辑比哈希表更贴近“计数的本质”代码短不易出错。更关键的是这种写法避免了哈希表的“哈希计算开销”。虽然哈希表在理论上也是O(1)的访问时间但实际运行时会有哈希碰撞、扩容等隐性成本。数组下标访问是零散列的直接寻址性能上要稳得多。我在本地用 10 万长度的随机字符串实测过数组法比字典法快差不多 30% 到 40%在力扣的评测环境里两者的耗时差距也很明显。4.3 一个常见疑惑为什么最后要单独遍历检查数组而不是在第二轮循环里判断负数我在写第一版代码的时候也是这么想的既然第二轮循环一直在减那我每减一次就检查一下count[index] 0发现负数就返回False不是能更早退出吗这个逻辑其实是对的而且可以这样写def is_anagram_early_exit(s: str, t: str) - bool: if len(s) ! len(t): return False count [0] * 26 for ch in s: count[ord(ch) - ord(a)] 1 for ch in t: index ord(ch) - ord(a) count[index] - 1 if count[index] 0: return False return True这种方式同样正确而且对大多数不匹配用例能提前终止理论上性能更好。但代价是代码里多了一个判断分支逻辑上没有“全部减完统一检查”那么直观。两种风格面试时都可以用我个人的习惯是手写的时候用统一检查因为不容易漏判边界情况讲思路的时候把“提前终止”作为优化项提一嘴这样既展示了代码的严谨性又体现了对性能细节的敏感度。5. 那些容易疏忽的边界条件和细节刷题最怕的不是不会做而是“以为自己做对了”。这道题有几个边界条件面试官几乎必考。5.1 长度先判断还是后判断强烈建议在做任何计数之前先判断长度。如果len(s) ! len(t)直接返回False。这不是为了节省时间而是为了让代码逻辑更清晰——长度不等的情况下后面所有计数操作都是无意义的。但是有个细节要注意在 Python 的Counter(s) Counter(t)这种写法里即使不手动判断长度结果也是正确的。因为两个Counter如果长度不同必然有某个字符的计数不同比较结果自然为False。所以长度判断在这里只是“防御性写法”不会改变结果。但在手写数组法的场景里如果你先遍历s再加计数再遍历t时发现某个字符的计数不够减而返回False那也依然正确。只是“先判长度”能让代码读者一眼看懂你的思路。5.2 字符串为空的情况两个空字符串是否互为字母异位词答案是肯定的。s t 两者的字符频率都是空映射为真。上面的几种写法都能正确处理空字符串排序法对空字符串直接相等字典法两个循环都不执行返回True数组法两个循环不执行检查全 0 数组自然也是True。面试的时候我会特意提一句“空串也适用”这种细节虽然不至于决定成败但能表现出考虑问题周全。5.3 大小写问题题目没说的部分LeetCode 原题限制输入仅包含小写字母所以不需要处理大小写。但实际项目中用户输入的字符串往往是大小写混杂的比如Listen和Silent这种经典字母异位词如果直接比较必然返回False因为L和l是不同的字符。如果要支持大小写不敏感比较最优雅的做法是统一转换为小写再计数s s.lower() t t.lower()然后复用原来的逻辑。注意这里还有个“坑”如果你直接调用str.lower()它会创建一个新字符串如果你在乎内存也可以遍历时用ch.lower()逐个处理。不过刷题场景下没必要过度优化统一转换最简单。5.4 Unicode 字符怎么办如果输入不只是小写英文字母而是包含 Unicode 字符比如中文、表情符号、emoji数组大小为 26 的方案就失效了。这里有两个路径路径一用哈希表计数字符天然作为字典的键完全支持任意 Unicode。路径二用 Python 的Counter本质上也是哈希表同样支持。所以面试官如果追问“如果字符范围扩大了你还能用数组吗”标准回答是“数组方案依赖于字符集有限且连续的前提字符范围扩大时退回哈希表复杂度仍然是 O(n)。”这个回答能体现出你对数据结构适用边界的理解。5.5 一个容易忽略的性能点提前返回要谨慎有些人写第二遍遍历时喜欢一旦发现某个字符在多出的情况下立刻返回False。这在绝大多数场景里是安全的但有一个前提你已经先判断了两者长度相等以及你使用的是“先加后减”的顺序。如果顺序反了比如先遍历t减计数再遍历s加计数那么提前返回的时机和位置就不一样了逻辑会变得非常绕。我建议新手老老实实按“先加后减”的固定套路写不要试图自作聪明改动顺序等熟悉了再尝试各种变体。6. 面试官爱问的变种和进阶追问一道 Easy 题在面试中通常不会止步于“写完就收工”。有经验的面试官会顺着你的答案往下挖掘深度这几个追问方向我基本都遇见过。6.1 追问一如果字符串非常非常长如何优化如果两个字符串长度达到 GB 级别内存放不下怎么办答案方向是“排序后逐块比较”或者“把字符分布统计到外部存储”。不过这种题在面试里很少真问到底因为太工程化了。更常见的是问“你能用 O(1) 的额外空间解决吗”注意这里的O(1)额外空间指的不是数组法的固定 26 长度而是能不能“原地修改输入字符串”由于字符串在 Java、Python 中是不可变的原地修改并不现实所以这种追问一般发生在 C/C 面试里。用 C 的话可以先对两个字符串排序然后逐字符比较排序本身用的是栈空间如果把排序实现为原地快排或堆排额外空间可以做到O(log n)甚至O(1)。但时间复杂度会退回到O(n log n)。所以这道题有一个经典的“不可能三角”想要O(n)时间、O(1)额外空间必须依赖字符集有限这个前提字符集无限时哈希表的空间代价是不可避免的。面试时能把这个 trade-off 讲清楚就已经赢了大多数候选人。6.2 追问二如何判断一组字符串里有多少对字母异位词这是力扣 49 题“字母异位词分组”的雏形。给定一个字符串数组要求把所有互为字母异位词的字符串分到同一组。核心思路是把每个字符串的“字符频率特征”作为哈希表的键。最常见的实现是对每个字符串排序后作为键或者统计 26 个字母的计数数组然后将其转成元组作为键。Python 代码大概是这样的from collections import defaultdict def group_anagrams(strs): groups defaultdict(list) for s in strs: key tuple(sorted(s)) groups[key].append(s) return list(groups.values())这里排序后作为键本质上和上面“排序法判断异位词”是一脉相承的。如果想追求更好的时间复杂度可以用计数数组转元组def group_anagrams_advanced(strs): groups defaultdict(list) for s in strs: count [0] * 26 for ch in s: count[ord(ch) - ord(a)] 1 key tuple(count) groups[key].append(s) return list(groups.values())这个写法在字符串较长时明显比排序法更优因为排序是O(n log n)而计数是O(n)。6.3 追问三两个字符串的“相似度”怎么算这里就引申到编辑距离、最长公共子序列等经典动态规划问题了。虽然不算严格的变种但面试官从字母异位词跳到“变位词相似度”是很自然的过渡如果你准备了 DP 基础可以顺着话题聊下去。不过这是另一个大话题这里不展开只提醒一句一旦面试官往这个方向引说明他对你的基础评价不错可以考虑继续深入展示。6.4 追问四流式场景如何处理如果两个字符串不是完整给出的而是以字符流的方式不断到达例如两个文件流需要实时判断是否为字母异位词这时一次性遍历的方案就得改造成“滑动窗口”模式。核心是维护一个长度固定的窗口实时更新计数并和另一个字符串的计数做对比。这是力扣 438 题“找到字符串中所有字母异位词”的思路属于本道题的进阶版本面试中考到的频率也相当高。7. 我总结的刷题笔记与建议这道题刷完我觉得最有价值的收获不是“我会做这道题了”而是它串起了一个完整的算法思维链条第一层拿到题目先想暴力法也就是排序比较确保自己能写出一个“绝对正确”的方案兜底。这个习惯在面试里非常重要因为面试官要求你出解法时最忌讳的是卡在那里一句话不说。哪怕先给一个O(n log n)的方案都比沉默强。第二层在暴力法的基础上优化。看到“字符出现次数”这种关键词条件反射地想到计数、哈希表、数组映射。这道题的字符集限制26 个小写字母是优化的抓手也是你展现复杂度分析的绝佳素材。第三层边界条件和变种训练。别急于提交一个能过的答案花两分钟想一想空串、大小写、Unicode、超长字符串、分组变种这些问题想一遍你对“字母异位词”这个概念的认识就立体了。我在实际准备面试的过程中习惯把每道题整理成一个模板核心包括四块题目理解、最优解思路、复杂度分析、变种方案。这道题我反复看了三遍每次都有新体会。第一遍看懂了哈希表解法第二遍体会到了数组法的精妙第三遍在面试前重新翻笔记的时候才真正理解了为什么面试官喜欢拿它当“热身题”——因为它能在五分钟内考察候选人三个关键能力代码基础是否扎实、是否能主动优化、是否具备边界意识。如果你目前还在刷题初期我建议不要跳过这道题也不要觉得它简单就只抄一遍答案。拿一张纸手写一遍数组法的代码再推演一遍复杂度再把Counter版本和数组版本的性能差异实际跑一下你会发现这道“简单题”真的不简单。等上面的追问都能流畅答出来的时候你面对字母异位词这一类题就真正稳了。
