做 LeetCode Hot100 的朋友应该都有体会字符串类的题目往往看着简单一上手全是细节。第49题字母异位词分组就是这么一道题给你一个字符串数组要求把由相同字母重新排列而成的单词归到同一组。题目本身一句话就能看懂但真正把它吃透你会理解一个很重要的思维模型——排序作为分组标识。这道题在 Hot100 里算入门偏基础的位置但它同时考察哈希表、字符串处理和状态归一化的思想值得花时间把两种主流解法都写一遍。我写这篇题解不会只贴代码重点是想把为什么排序后可以作为同一组的标识这件事讲透再把排序哈希到计数分组映射的演进过程拆开说清楚最后补充一些我自己踩过的坑和面试追问的思路。如果你正处在刷题初期看完这篇文章应该能对这类分组重排问题建立一套稳定的解法模板。1. 先读懂题目字母异位词到底在考什么1.1 题目一句话输入、输出与隐藏规则LeetCode 49 的题干很简短给定一个字符串数组将字母异位词组合在一起。所谓字母异位词就是由相同字母重新排列形成的单词比如eat、tea、ate用的都是 e、a、t 三个字母只是顺序不同它们就该归为一组。真正需要留意的隐藏规则有两条。第一输入数组的长度 n 和单个字符串的最大长度 k 都可能在 0 到 100 之间浮动原题给出的约束是字符串长度不超过 100这意味着空字符串也是合法输入任何解法都要把空字符串当成一个普通分组来处理。第二原题默认所有字符串只包含小写字母这一点非常关键它直接决定我们能不能用int[26]这种定长数组做字母计数而不是更笨重的HashMapCharacter, Integer。我在面试现场见过不少人拿到题目就开始写排序却忽略了字符集假设等面试官把输入改成大写字母时当场卡壳。题目要求输出顺序没有硬性规定所以返回ListListString时分组顺序、组内顺序都可以任意。很多题解喜欢按出现顺序输出但如果你想要稳定的字典序就要额外对组内元素排序。这个任意顺序不是废话它意味着我们可以放心依赖哈希表的无序特性不用担心输出顺序影响判题。1.2 为什么这道题能进 Hot100Hot100 选的是面试里出现频率最高、又最能考察基础数据结构和算法思维的题目。49 题几乎完美踩中了三个高频考点哈希表的使用、字符串处理、以及状态归一化的思想。它不涉及复杂的动态规划不需要背模板但能在一道题里同时考你对 HashMap 底层机制的理解、对字符数组排序 API 的熟练度以及能不能想到用某种标识把不同表示统一起来。更重要的是这道题的两种主流解法分别代表了两种复杂度思路。排序哈希是先排序再分组的直给方案计数映射是用统计特征代替排序的优化版本。很多经典字符串问题比如检查两个字符串是否互为异位词、找出数组中所有重排后相同的词本质上都是同一个套路。把 49 题吃透后面再遇到类似题目你的脑子里会有一个模板可以套而不是每次从零开始硬想。2. 核心问题为什么排序后可以作为同一组的标识2.1 异位词的本质是字母多重集要理解为什么排序能当分组标识先得想清楚异位词的数学本质。两个字符串互为异位词意味着它们每个字母的出现次数完全相同只是排列顺序不同。用集合论的术语说它们共享同一个字母多重集multiset——集合里允许重复元素但不管顺序。eat的多重集是 {a:1, e:1, t:1}tea和ate的多重集也是 {a:1, e:1, t:1}所以它们是一家人。eat和bat呢前者是 {a:1, e:1, t:1}后者是 {a:1, b:1, t:1}e 和 b 不一样多重集不同就不是异位词。这个视角非常重要。一旦你把问题从两个字符串能不能重排成对方转换成两个字符串的多重集是否相同就找到了一个统一的判定标准。接下来要做的就是设计一个函数把任意字符串映射成一个不依赖字母顺序的稳定特征值特征值相同的进同一组。2.2 排序是一种归一化操作把无序变成有序把字符串排序本质上就是对这个多重集做一次归一化normalization把字母按字典序固定排列把原本无序的信息变成有序的规范形式。归一化之后eat变成aettea变成aetate也变成aet三者得到同一个字符串因此可以共用一把钥匙。为什么这个操作是可靠的因为排序只依赖字母的内容和数量与原始顺序无关。你可以把排序想象成把一袋积木按大小重新码好袋子里有哪些积木、每种有几块是固定的怎么摆都不影响最后码好的序列。反过来如果两个字符串排序后结果相同那说明它们包含的字母种类和数量完全一致必然互为异位词。这是一个双向的充要条件所以排序结果作为分组标识不会产生误判。这里有一个关键细节排序后的字符串是规范化键它本身可能不是任何原始字符串这不重要它只是用来分组的编号。就像快递运单号快递内容千差万别运单号只是归类用的标签。2.3 哈希表的键就是分组标识有了规范化键分组就只是哈希表的一层皮遍历每个字符串算出它的规范化键以键为 key、以组列表为 value 塞进 HashMap。如果键已存在就把当前字符串追加到对应组的末尾如果不存在就新建一个列表并放入。最后把 HashMap 的所有 value 收集起来返回。哈希表在这里承担的角色是分组桶。HashMap 基于键的 hashCode 和 equals 工作字符串的 hashCode 和 equals 正好能正确区分不同键。这个组合非常自然String 在 Java 里是不可变对象哈希值稳定equals 按内容比较所以它作为 key 非常安全。如果你尝试用int[26]数组直接做 keyJava 数组的 equals 继承自 Object比较的是引用地址两个内容相同的int[]不会相等HashMap 就会把它们当成不同键这是很多初学者掉进去的坑。3. 方案一排序哈希最直观的写法3.1 Java 实现toCharArray Arrays.sort排序哈希的代码很短核心就是三步转字符数组、排序、拼回字符串。我直接贴出可以运行的版本public ListListString groupAnagrams(String[] strs) { MapString, ListString map new HashMap(); for (String s : strs) { char[] arr s.toCharArray(); Arrays.sort(arr); String key new String(arr); map.computeIfAbsent(key, k - new ArrayList()).add(s); } return new ArrayList(map.values()); }先说一个容易忽略的点不要用StringBuilder手动把 char[] 一个个 append 回去。直接new String(arr)就行Java 的 String 内部有专门针对 char[] 的构造方法效率更高代码也更干净。computeIfAbsent是 Java 8 引入的 API它做了三件事检查 key 是否存在不存在则用 lambda 创建默认值存在则直接返回已有列表。这个写法比先containsKey再get再put清爽很多也避免了重复查询哈希表的开销。如果你的项目还在用老版本 Java就需要写成下面这样ListString list map.get(key); if (list null) { list new ArrayList(); map.put(key, list); } list.add(s);两种写法都可以但如果你在面试时写出computeIfAbsent通常会被视为熟悉现代 Java API印象分会好一些。3.2 Python 实现sorted 的简洁写法如果你用 Python这题的代码会更短。Python 的sorted(s)返回字符列表用.join(...)拼回字符串配合collections.defaultdict(list)几乎是一行核心逻辑from collections import defaultdict def groupAnagrams(strs): groups defaultdict(list) for s in strs: key .join(sorted(s)) groups[key].append(s) return list(groups.values())这里有个小坑sorted(s)返回的是字符列表列表本身不可哈希所以不能直接当字典的 key必须先 join 成字符串。有人可能想到用tuple(sorted(s))做 key这在语法上可行因为元组可哈希但元组里每个元素都是单字符内存占用比字符串更散性能上不如 join 来得干脆。Python 的defaultdict(list)在面试时是加分写法它免去了判断 key 是否存在的样板代码。如果你担心面试官不理解 defaultdict可以在开头手写初始化或者用group groups.setdefault(key, [])达到类似效果。3.3 复杂度分析O(nk log k) 是怎么来的设输入的字符串数组长度为 n其中最长的字符串长度为 k。排序哈希方案的时间复杂度是 O(n * k log k)每个字符串都要做一次排序排序本身是 O(k log k)一共 n 个字符串所以整体是 O(nk log k)。空间复杂度是 O(nk)。为什么因为 HashMap 里每个字符串都会被存进某个分组列表所有字符串加起来的总字符数是 O(nk)。此外哈希表的键也是排序后的字符串长度同样为 O(k)n 个键还会贡献额外的空间但在大 O 表示下仍然收敛到 O(nk)。理解了复杂度你就能判断什么时候排序哈希不够好。如果 k 非常小比如字符串平均长度只有 2 到 3排序和扫描几乎没差别排序哈希就是首选但如果 k 很大比如一个字符串有 100 个甚至 1000 个字符排序的 log k 因子就会变得刺眼这时你就应该考虑下一节讲的计数分组映射。4. 方案二计数分组映射把排序换成统计4.1 思路用每个字母的出现次数做键计数分组映射想解决的问题很明确去掉排序带来的 O(k log k)把每个字符串的处理时间压到 O(k)。思路是既然异位词的判定只取决于每个字母出现几次那我干脆不排序而是用一个定长计数器统计字符串里每个字母的频次再把频次序列编码成一个可哈希的键。两个字符串如果每个字母出现次数都一样它们的键就一样自然分到一组。这个方案建立在题目只含小写字母的假设上所以能用int[26]数组做计数器。26 个位置分别对应 a 到 z遍历字符串时把对应位置的计数加一。关键在于如何把这个int[26]变成一个合法的 HashMap 键这需要一点设计技巧。4.2 Java 实现int[26] StringBuilder 拼键先看完整代码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]; } StringBuilder sb new StringBuilder(); for (int i 0; i 26; i) { if (count[i] 0) { sb.append((char) (a i)); sb.append(count[i]); } } String key sb.toString(); map.computeIfAbsent(key, k - new ArrayList()).add(s); } return new ArrayList(map.values()); }拼键的细节值得展开。我选择只把出现次数大于 0 的字母拼进去格式是字母 次数例如eat得到a1e1t1aba得到a2b1。这种稀疏拼接有两个好处第一键的长度最多只与字符串中不同字母的种类数相关而不同字母数最多 26所以即使字符串本身很长键长也不会失控第二键里同时包含字母和频次可读性强排查问题的时候一眼能看出该组的构成。网上有些写法会把 26 个位置的计数全部拼出来比如1#0#0#...这也能工作但字符串会很长占内存且没有必要。我的建议是始终坚持稀疏拼接效率更高。这里必须强调一个 Java 特性数组不能直接作为 HashMap 的键。Java 数组的equals和hashCode都是从 Object 继承的引用版本两个内容完全相同的int[26]也被视为不同对象所以直接用数组当 key 会得到错误的分组结果。但在 Python 里tuple(count)可以直接当作字典键因为元组的哈希和比较都被正确实现了。这也是语言特性影响数据结构选型的一个经典例子。4.3 两种方案的对比与选型我把排序哈希和计数映射放在一起对比维度排序哈希计数分组映射单字符串处理时间O(k log k)O(k)总时间复杂度O(nk log k)O(nk)空间复杂度O(nk)O(nk)键可能更短实现难度最简单略复杂需要拼键键的可读性排序字符串直观频次编码需要解释处理非小写字符不受限需要调整计数数组大小选型建议大多数情况下我推荐先写排序哈希。它代码短、思路直白、几乎没有出错空间面试时先把正确解法交出来比什么都重要。如果面试官继续追问优化再抛出计数映射展示你注意到排序是瓶颈、能设计出 O(nk) 的方案这会给人一种你系统掌握两种复杂度思维的感觉。如果题目明确说字符串长度很大或者你在讨论中需要强调最坏情况下的稳定性计数映射才是更稳的选择。实际跑 LeetCode 的测试数据两种方案都能通过因为数据量不大差异在常数层面几乎看不出来但理论学习上它们代表了两条完全不同的路。5. 实操避坑键冲突、边界输入与语言差异5.1 计数键会不会冲突分隔符与歧义问题新手最容易担心的问题拼接出来的计数键会冲突吗比如a2b1代表 2 个 a 和 1 个 b有没有可能另一个字符串也拼出a2b1但实际频次不同不会。因为格式里字母和数字是一一交替的a2b1只能解析成 a 出现 2 次、b 出现 1 次没有任何歧义。但如果你为了省事只把数字拼在一起比如21代表 a 出现 2 次、b 出现 1 次问题就出现了a出现 21 次会拼出21a出现 2 次且b出现 1 次也可能拼出21。这就是键冲突。所以计数键的设计必须包含字母本身或可靠的分隔符否则就埋了雷。同理如果字符串中包含数字字符本身而且字符集扩大到 ASCII计数数组要扩容到 128拼键时也需要更鲁棒的分隔。面试时如果被问到字符集不限于小写字母我的建议是干脆改用排序哈希或者用HashMapCharacter, Integer做计数再拼键代码会繁琐很多但能明确规避冲突。5.2 边界输入空数组、单元素、空字符串边界条件在 LeetCode 里是最容易翻车的地方。空数组[]的情况不管排序哈希还是计数映射遍历循环一次都不执行返回new ArrayList(map.values())会得到空列表没问题。数组只有一个元素[abc]会生成一个分组[abc]也没问题。最容易忽略的是空字符串。空字符串排序后还是空串计数后所有 count 都是 0拼出的键是空串。所以所有空字符串会聚到同一个分组里这符合它由 0 个字母组成的定义。如果你在实现时对空串做了特殊处理反而画蛇添足。还有一个实际测试中常见的输入字符串里有大量重复字符比如aab、aba、baa。排序哈希的键都是aab计数映射的键都是a2b1都能正确归组。重复字符意味着分组里可能包含多个结构相同但排列不同的字符串这正好是题目要处理的场景。5.3 语言与编码差异大写字母、非字母字符怎么办原题明确是小写字母所以int[26]够用。如果题面改成包含大写字母计数数组就得扩到 52或者直接用 ASCII 128。更稳妥的做法是只对字母字符计数或者把字符串全部转成小写再处理但后者会改变原始值结果可能不符合题目要求。我在实际写题解时踩过一个坑把字符换算索引时忘了处理字符集。c - a对A会算出负数数组越界直接抛异常。所以如果你在本地练习时自定义了包含大写字母的测试用例一定记得同步修改实现单纯靠 LeetCode 默认用例是测不出这个问题的。另一个语言差异是 Java 的new String(arr)和 Python 的.join(sorted(s))在底层实现差别很大但结果一致。真正影响选型的是键的数据类型Java 只能用不可变对象做 keyPython 用 tuple、frozenset 都可以。如果团队代码风格偏函数式甚至可以用 reduce 拼接计数键但我个人不建议为了炫技牺牲可读性。6. 常见问题速查与面试追问6.1 速查表什么问题对应什么解法问题原因解法分组结果顺序不稳定依赖哈希表遍历顺序题目允许任意顺序无需处理如需稳定返回前对每组排序计数键冲突只拼数字未带字母或分隔符键用字母次数格式确保一对一解析数组越界异常输入含大写或非字母字符确认字符集扩展到 int[128] 或改用排序哈希空字符串分组异常担心 key 为空串空串本来就该归为同一组不要特殊处理用 int[] 直接做 key 分不了组Java 数组 equals 是引用比较转成 String 或使用其他不可变键内存占用偏高每个字符串都要存进列表这是题目要求的一部分无法避免键可以尽量缩短这张表基本覆盖了我在评论区见到的高频提问。技术面试题往往卡在看似对但结果不对的边界上提前扫一遍这些坑能省很多调试时间。6.2 面试官可能的追问能不能只遍历一遍、能省空间吗追问一能不能在 O(nk) 时间内解决答案是能用计数映射。追问二能不能不用额外存储键这就要分情况了。排序哈希必须存排序后的字符串计数映射的键通常比原字符串短两种方案都没法完全省掉分组列表的空间因为题目要求返回所有分组结果本身就要占 O(nk) 空间。追问三如果只需判断两个字符串是否互为异位词空间能否更省可以。用计数数组对两个字符串分别统计后比较或者原地排序后比较字符串空间从上面的分组场景大幅下降。这其实是在考察你是否能把分组问题和判断问题区分开两组的路数不一样。我见过面试官从 49 题一路追问到字符串哈希、多重集比较、甚至布隆过滤器本质想看你能否把一个简单的分组思路迁移到更复杂的场景。答不出来不是最可怕的可怕的是连这题是不是考哈希表都说不出所以然。把排序哈希和计数映射的复杂度、键的设计、边界处理都准备好这个追问环节基本不会冷场。7. 延伸思考从这题你能带走的通用套路7.1 归一化 哈希分组是一个通用模式字母异位词分组的本质可以抽象成一句话先归一化再哈希分组。归一化就是把一个对象映射到某种规范形式让等价的对象得到同一个表示哈希分组就是用这个规范形式充当 key把同类对象收进同一个桶。这个模式不只适用于字符串。举例来说判断两个多项式是否本质相同可以比较它们的标准展开判断两个二维平面上的点是否关于某个变换等价可以先做坐标变换再比较。凡是要把形态不同但本质相同的对象归类你都应该先想有没有一个稳定的归一化函数。排序就是最通用的归一化函数之一因为它不依赖额外参数任何可比较元素都能排序。计数则是更精细的归一化它利用题目对字符集的约束用更少的时间得到同样的效果。这两种思想会在很多 LeetCode 题里反复出现比如判断所有子串中哪些互为异位词、找出所有可以由某个单词重排得到的序列等。7.2 这类题还可以怎么变着考最常见的变体是把字母异位词改成数字的排列组合或者要求你输出每个分组内的排序结果。再进阶一点题目可能让你找出所有互为异位词的分组但字符串数量非常大内存放不下那就需要引入外部排序或分桶策略这时候哈希键的生成方式会影响分桶是否均匀。另一个变体是最多能分成多少组或者是否存在某个组包含给定单词这类问题本质上还是同一套分组逻辑只是把查询需求从返回全部分组变成了判断成员关系。掌握好排序哈希和计数映射这些变体基本就是改几行代码的事。最后说点题外话。我刷过好几轮 Hot10049 题每次都能给我一点新感觉第一轮刷的时候只会排序哈希第三轮开始意识到计数映射在长字符串上的优势后来给别人讲题发现大家最容易漏掉的就是字符集假设和键的解析这两个点。如果你也是初阶玩家我的建议是不要满足于通过把两种解法各写一遍再对着边界输入测试一遍这个过程比连续刷十道简单题更有价值。这道题的为什么排序能做标识想明白了后面很多字符串题都会变得豁然开朗。