先聊个面试现场常遇到的场景。你面前正坐着面试官对方在白板上写下了一道题给定一个字符串数组请你将字母异位词组合在一起。 如果你没有准备过这类手写代码题第一反应多半是异位词是什么——其实说白了就是由相同字母、相同数量重新排列得到的单词。比如 eat、tea、ate三者互为字母异位词而tan和nat又是一组。这道题在算法面试里的地位相当于编程界的 hello world加快速排序的结合体看起来简单却能一次性考察你的哈希表运用、字符串处理、复杂度分析甚至沟通习惯。无论你是在准备实习、校招还是社招跳槽这道题都值得认真手写一遍吃透背后的思维方法。我当年刷这道题时市面上解答五花八门有人用排序做key有人用计数数组做key还有人用质数乘积硬做。到底哪种方案是标准答案其实没有标准答案只有在什么约束下选什么方案。这篇文章把我手写这道题的全过程拆开从思路演进到两种主流实现再到面试现场如何应对追问、避开常见坑一步步说清楚。1. 字母异位词分组的本质从暴力匹配到哈希归并1.1 题目的隐藏条件与信息抽取先看题目的原始描述给定一个字符串数组要求把字母异位词组合在一起。注意几个关键点。第一输入的单元不是单个字符串而是一个数组这决定了你需要在多组数据之间建立关联。第二字母异位词的定义是字母构成相同、每个字母出现次数相同顺序可以不同。第三输出要求是分组即把具有相同特征的字符串归到同一个列表里最终返回一个嵌套列表。把这些条件翻译成计算机能处理的逻辑核心就一个问题如何给两个字符串建立一个相等的判断标准如果每次都用双层循环逐个字符比对每个字符串的字母频率时间会爆炸。假设数组里有N个字符串每个字符串平均长度为K暴力两两比较一组字符串需要O(K)的时间而全部两两比较需要O(N^2)次整体复杂度就是O(N^2 * K)。面试官看到这个复杂度多半会摇头。所以这道题的破局点在于能不能给每个字符串算出一个签名让所有互为异位词的字符串拥有同一个签名然后按签名分组这正好是哈希表的用武之地——签名就是key分组结果就是value。1.2 特征提取思维排序和计数是两条主流路线给字符串提取特征最直觉的做法是让字面顺序统一。字符串内部字母怎么排列不重要那就把它从小到大排序。排序之后eat变成aettea变成aetate也变成aet三者共享同一个key。这种思路的优点是实现极其简单代码量少缺点是引入了排序的O(KlogK)成本。另一条路线是统计每个字母的出现次数。既然异位词的字母频率完全相同那把每个字符的频率记录下来作为特征。对于字符串eat可以记为a:1, e:1, t:1tea、ate的频率字典也完全一致。这种思路不需要排序只需扫描一遍字符串统计频次时间复杂度是O(K)比排序更优但构造key时需要把频率信息序列化成一种可哈希的形式比如拼接成1a1e1t这样的字符串或者转成固定长度数组。两种路线都能解决问题区别在于工程实现和测试场景。排序法更通用即使字符集很大比如Unicode字符也能用先排序再拼接处理计数法在字符集固定且较小比如只有26个小写英文字母时更高效但要小心key的构造方式不能有歧义。提示面试中优先推荐排序法因为代码短、逻辑清晰、不容易写错。如果面试官追问能不能优化到O(NK)再切换到计数法。这既能展示你的优化意识又不会让第一步陷入复杂实现的泥潭。2. 手写实现方案一排序分组法三分钟写出的稳妥解2.1 核心逻辑与代码实现排序法的实现路径非常直白遍历输入数组对每个字符串排序用排序结果作为哈希表的key把原字符串追加到对应的value列表中。最后把哈希表的全部value取出来就是分组结果。我给出Python和Java两个版本方便你对照。Python版本from typing import List def groupAnagrams(strs: List[str]) - List[List[str]]: # 哈希表排序后的字符串 - 原始字符串列表 groups {} for s in strs: # 关键步骤排序并拼接回字符串作为key key .join(sorted(s)) if key not in groups: groups[key] [] groups[key].append(s) # 返回所有分组不关心组间顺序 return list(groups.values())Java版本import java.util.*; public class Solution { public ListListString groupAnagrams(String[] strs) { MapString, ListString map new HashMap(); for (String s : strs) { // 将字符数组排序后转为字符串作为key char[] arr s.toCharArray(); Arrays.sort(arr); String key new String(arr); // computeIfAbsent 简化判空逻辑 map.computeIfAbsent(key, k - new ArrayList()).add(s); } return new ArrayList(map.values()); } }这段代码的精髓在于sorted(s)这个动作。很多人会问排序字符串不是要O(KlogK)吗没错所以整个算法的时间复杂度是O(NKlogK)其中N是字符串数量K是字符串最大长度。空间方面哈希表里要存储所有字符串的key和value总体空间O(NK)。2.2 排序法的时间消耗与适用场景排序法的代码足够简短但有一个隐藏陷阱如果字符串非常长比如每个字符串几千个字符那么排序的O(KlogK)成本就会明显放大。我在实测中试过当K达到10万级别时排序耗时已经肉眼可见地拖慢整体性能。所以排序法更适用于字符串平均长度较短的场景这也是LeetCode原题的数据范围字符串长度多数在个位数到十几位能直接AC的原因。还有一个值得注意的细节Python的sorted(s)返回的是字符列表必须用.join()重新拼成字符串才能作为哈希表的key。直接拿列表当key会直接报错因为列表是不可哈希的。语言细节虽然简单但手写代码时往往会因为紧张忽略掉导致现场一跑就挂。注意排序法对非英文字母字符也有效比如中文、数字、符号只要字符的排序规则一致互为异位词的字符串排序结果必然相同。这也是排序法的一个附带优势——不需要假设字符集只有26个小写字母。3. 手写实现方案二计数分组法把时间复杂度压到O(NK)3.1 用数组计数构造无损key计数法的出发点很简单字母异位词的字母出现频率完全相同所以我只要统计每个字符出现几次就能得到一个特征向量。对于只包含小写字母的字符串可以用一个长度为26的数组统计频次数组的每个位置对应一个字母。然后的问题是怎么把数组变成哈希表的key常见做法有两种。第一种是把数组转成一个定长字符串比如每个位置写成字母次数的格式像a1e1t1。第二种是把数组转成元组Python的tuple直接作为key因为元组本身是可哈希的。第二种写法更优雅但Java没有直接的元组需要手动拼接字符串。Python计数版本from typing import List def groupAnagrams(strs: List[str]) - List[List[str]]: groups {} for s in strs: # 统计每个字母出现次数 count [0] * 26 for ch in s: # ord(ch) - ord(a) 得到字母在数组中的下标 count[ord(ch) - ord(a)] 1 # 转成元组作为key key tuple(count) if key not in groups: groups[key] [] groups[key].append(s) return list(groups.values())Java计数版本用拼接字符串作为keyimport java.util.*; public class Solution { public ListListString groupAnagrams(String[] strs) { MapString, ListString map new HashMap(); for (String s : strs) { int[] count new int[26]; for (char c : s.toCharArray()) { count[c - a]; } // 拼成 a1e1t1 形式注意补上字母本身避免歧义 StringBuilder sb new StringBuilder(); for (int i 0; i 26; i) { if (count[i] 0) { sb.append((char) (a i)).append(count[i]); } } String key sb.toString(); map.computeIfAbsent(key, k - new ArrayList()).add(s); } return new ArrayList(map.values()); } }这个方案的复杂度是O(NK)因为对每个字符串只需要扫描一遍统计频次再构造key。构造key的过程也是O(K)量级更准确地说是O(26)或者取决于字符集大小。整体时间比排序法提升了一个log因子在字符串特别长时优势明显。3.2 决定计数法成败的key设计细节计数法看似简单坑却藏在key的设计里。如果我只把频次拼接成113不带上字母本身那abc1个a、1个b、1个c和111这种字符串就会产生歧义吗实际上不会因为key的语义完全由频次数组决定。但如果在拼接时写成111那abc和aaa在某种拼接方式下可能产生同样的key我们来看abc的频次数组是[1,1,1,0,0...]aaa的频次数组是[3,0,0,...]。如果把频次数组直接转成字符串111000...3000...其实不会重复因为数组长度固定是26、每个位置对应固定字母。但如果我偷懒只统计有出现的字母拼接字母次数比如a1b1c1对应abca3对应aaa同样不会有歧义。真正会出问题的是某些编码方式比如把频次压缩成111不带字母信息abc和bc这类无法区分实际上频次数组长度固定为26时压缩后不同字符串也可能产生相同序列比如abc频次为1,1,1,0...bc频次为0,0,1,1,0...如果去掉字母只写次数前者是111000...后者也是011000...并不会混淆但如果进一步压缩成连续次数形式就可能有风险。所以行业实践中有一套安全约定要么用完整定长数组转tuple要么拼接时带上字母本身。我强烈建议面试手写时优先使用Python的tuple版本或者Java中带上字母次数的拼接这样最稳妥也不会让面试官质疑key的唯一性。实操心得计数法设计key时最容易翻车的不是统计过程而是key的序列化过程。如果只用频次数字拼接可能出现不同字母分布却得到相同key的极端情况带上字母本身后这个问题从根上消失。这个细节我踩过坑后来形成习惯只要涉及频次转key一律带上字符标识。4. 面试手写现场从读题到AC的完整动作拆解4.1 写代码前的黄金三问很多候选人一看到这道题就开始埋头写代码结果要么写一半卡住要么写完发现偏离需求。我自己的习惯是拿到题目先问自己三个问题输入范围是什么字符串里的字符集是什么输出结果的顺序有没有要求第一个问题决定了算法选型。如果数组长度很大、字符串很长就要考虑O(NK)的计数法如果只是常规面试规模排序法完全够用。第二个问题决定了能不能用固定长度数组。如果题目没说明只含小写字母直接开count [0] * 26就是刻舟求剑这时候排序法的通用性反而更好。第三个问题关系到输出细节。大部分题目不要求组内顺序和组间顺序但个别变体会要求每个分组内按字典序输出这就需要额外排序。这三个问题问完你不仅能选择合适的方案还能在动手前和面试官对齐需求——这种行为本身就会加分它说明你不是一个只会背题的人而有真实的工程思维。4.2 手写代码的节奏控制与自我检查手写代码不是越快越好而是稳中带快。我的建议节奏是先在白板上写出核心逻辑的伪代码框架比如遍历字符串 - 计算key - 存入哈希表 - 输出values再逐步填充语言细节。这样可以避免在中途陷入某一行语法的细节里而忘了整体结构。写完代码之后一定要做一个静态自查检查哈希表的初始化和更新逻辑是否正确、key的构造是否有歧义、边界输入是否报错。比如空数组输入时应该返回空列表而不是空指针异常空字符串应单独成为一组排序后依然为空字符串计数组全为0两者都能正确处理。自查完成后主动跑一个简单测试用例把整个过程口述给面试官听。以[eat, tea, tan, ate, nat, bat]为例eat排序为aet进入分组aettea排序也为aet追加到aet分组tan排序为ant新开一组ate排序为aet追加nat排序为ant追加bat排序为abt新开一组。最终输出三个分组。 这一步非常关键它能直观地向面试官证明你的代码逻辑是对的也给你自己一个复查的机会。4.3 如何处理follow-up从排序到计数的优化引导面试官问完这道题后几乎必问一句能不能优化时间复杂度 这就是展示深度的时候。你可以这样回答当前实现的时间复杂度是O(NKlogK)瓶颈在于对每个字符串排序。如果字符串只包含小写英文字母我可以把排序换成计数用长度为26的数组统计每个字母出现次数把数组序列化成key时间复杂度降到O(NK)。代价是代码复杂度略高且key的序列化需要额外空间。如果字符集扩展到完整的Unicode字符集计数数组的维度就会膨胀这时候可能不得不退回排序法或者用哈希表记录每个字符的频次。这套回答既展示了优化能力又体现了工程判断力——知道什么时候该优化、什么时候优化不划算。面试官一般都会对这样的分析点头。5. 高频易错点与工程扩展这道题背后的真实应用5.1 六个容易当场翻车的问题速查我把这道题最常见的错误整理成一个速查表手写之前过一眼能避开大多数坑。问题错误表现正确做法排序后忘记joinPython中sorted(s)返回字符列表直接当key报错.join(sorted(s))Java数组比较用Arrays.equals比较count数组但HashMap不会帮你自动比较把count数组序列化成String作为key忽略空字符串空字符串排序或计数结果与某些字符串冲突空串的key应独立存在排序法为空串计数法为全0假定字符集大小题目没说明只有小写字母就开长度为26的数组先和面试官确认字符集范围返回值类型不对Python返回dict_values对象而不是List[List[str]]用list(groups.values())转换修改原字符串直接对原字符串排序影响了后续操作复制到临时变量或使用不可变方法Python中字符串不可变天然安全Java需注意s.toCharArray()前四条是白板手写时的重灾区。我见过太多候选人栽在忘记join和Java数组直接当key这两个问题上代码逻辑全对一运行就崩。这些细节在IDE里靠编译器提示就能发现但在白板上就得靠平时练习形成的肌肉记忆。5.2 从算法题到工程实践异位词分组的真实用途这道题看起来像纯粹的面试题但它的底层思想在真实工程里到处可见。最简单的例子是拼写纠错系统用户输入recieve系统要猜测他可能想打的是receive这时候可以把词典里的单词按字母异位词分组同组的单词作为候选纠错选项。搜索引擎的索引构建也有类似逻辑对网页内容做单词规范化时把异位词归并建立映射可以提升查询匹配的召回率。另一个有意思的场景是数据脱敏与身份隐匿。我在一个日志分析项目里遇到过需求需要把一批用户昵称分组识别出那些只是打乱字母顺序、本质相同的内容用于发现重复注册的水军账号。直接两两比较昵称会非常慢用异位词分组的思想先对每个昵称提取排序key再按key归并几百万条数据也能在数分钟内完成分组。那一刻我才意识到面试题不是纸上谈兵它就是在教你怎么用哈希表解决真实世界里的归约问题。5.3 进阶变体从分组到回文、字谜索引等扩展掌握了基础版本后有几个典型的变体题值得顺带练习。第一个是判断两个字符串是否互为字母异位词只需要比较两个字符串的排序结果或频次数组连哈希表都不用。第二个是找到字符串数组中所有的异位词分组并按组内字典序排序在基础题上增加一个排序步骤即可。第三个稍微复杂一些给定一个字符串s和一个单词列表找出列表中所有可以由s的字母异位词组成的单词这需要结合滑动窗口和频次匹配。最经典的一个进阶变体是LeetCode 438找到字符串中所有字母异位词的起始索引。给定一个长字符串s和一个模式串p找出s中所有p的异位词子串的起始位置。这个题的解法是从基础分组题演变而来的维护一个长度为len(p)的滑动窗口每次滑动后比较窗口内字符串和p的频次数组是否相等相等就记录起始位置。学会了基础题的计数法这个变体几乎能直接套用区别只是把全量分组改成了局部匹配。这些变体看似在增加难度核心不变——始终围绕特征提取哈希归并这两个动作。把一道题吃透胜过刷十道相似但不懂原理的题。6. 我的个人实操总结与建议这道题我在面试别人和准备自己的面试时反复遇见过。每次看到候选人直接写出排序法我基本会默认他刷过题但当他能主动讲出排序法的问题在于O(KlogK)如果字符集固定我能用计数法降到O(NK)时我才会真正认可他的算法功底。所以我的建议是基础解法要快、要稳优化思路要清晰、要能算复杂度两者缺一不可。实际手写时我个人的经验是优先排序法打底然后根据面试官的引导切换到计数法。不要在第一时间就写计数法因为计数法的key构造比排序法复杂手写时更容易引入隐蔽bug万一白板写崩反而得不偿失。先给一个能跑通的方案再展示优化能力这才是面试中最稳妥的策略。最后分享一个自查小技巧写完代码后不要急着喊完成了先在脑子里执行一个最小用例从第一行代码走到最后一行。这个习惯不只能帮你发现语法错误还能在面试官面前展示你严谨的思维过程。手写代码的核心从来不是记忆力而是把一道题拆解成特征提取、哈希归并、复杂度权衡这种模块化思考的能力。这道字母异位词分组就是一个极好的训练样本。