前两天帮一个准备跳槽的朋友过LeetCode高频题刷到第49题“字母异位词分组”时他三分钟写出了排序法却答不上来“为什么计数法更适合超长字符串”这种追问。这个画面我见过太多次——题目本身不难但大多数人在背解法没吃透“异位词”背后的签名思想。借着这篇分享我打算把这道题从题意、三种解法、复杂度分析到工程落地完整拆一遍。适合两类人看一类是正在准备算法面试、想把高频题刷透的同学另一类是在业务里做文本归一化、重复数据识别的工程师。因为字母异位词分组不只是一道题它抽象出来就是“给一组字符串找一个稳定的规范化签名再按签名聚类”这个能力放到商品标题去重、变体文本风控里同样成立。先把这个题最底层的需求拆明白。1. 这道题到底在考什么字母异位词的前世今生1.1 从题目描述出发画清楚边界所谓字母异位词就是字母组成完全相同、只是排列顺序不同的字符串。最经典的例子是eat、tea、ate这三个词字母集合都是{a, e, t}各自出现次数也完全一样所以它们互为异位词。而tan和nat又是一组字母集合是{a, n, t}。bat和前面的词共享a和t但多了一个b少了e或n所以不能混进前面任何一组。题目给一个字符串数组要求把所有互为字母异位词的字符串放进同一个列表最终返回一个二维列表每一组内部的顺序、以及各组之间的顺序都不限制。边界条件很容易被忽略数组可能为空结果是[]数组里可能有空字符串多个空字符串应该归到同一组也可能有大量重复字符串比如 50 个abc它们同样要待在一个桶里。一个容易混淆的细节题目默认输入只包含小写字母所以处理时可以直接用ord(ch) - ord(a)映射到 0 到 25。如果面试官没有明确说你可以在解法里补一句“我按题目约定输入为小写字母”这样既严谨又给后面的扩展讨论留了话口。1.2 为什么它值得反复刷这道题是哈希表应用里的“样板题”核心考点只有两个第一识别异位词的不变量第二设计一个合适的哈希键。所谓不变量指的是无论字母怎么重排每个字母出现的次数不会变。换句话说eat变成tea只是位置换了频次表依然是一份a:1, t:1, e:1。抓住这个不变量所有解法都围绕同一件事展开把“无法直接比较的字符串”转换成一个“规格化的签名”再以签名为键做聚合。这也是为什么这道题被各大厂反复翻牌。一个面试者如果只会写排序法说明基本能力过关如果能主动说出计数法、分析两种方案的复杂度差异说明对哈希键的设计有理解如果再能把质数乘积的数学思路拿出来当彩蛋同时指出其工程隐患那基本就站在了第一梯队。从工程视角看这道题的价值更直接。我在做数据清洗时遇到过商品标题去重很多卖家会把“三文鱼刺身”改成“刺身三文鱼”重新铺货肉眼一看就是同一件商品但字符串直接比对怎么都对不上。后来用的方案本质上就是字母异位词分组的思路只不过把“字母”换成了“词”。因此这题值得反复刷而且刷的时候最好带着“这套签名逻辑能搬到哪”的思考去理解。2. 解法一排序字符串当哈希键最直观也最容易被面试官追问2.1 思路一句话代码八行如果把一个字符串内部的字母按字典序排好异位词就会得到同一个结果。比如eat、tea、ate排序后都是aettan和nat排序后都是ant。这样排序后的字符串就成了一种规范化签名直接作为哈希表的键原字符串作为值塞进对应列表。from collections import defaultdict def group_anagrams(strs): groups defaultdict(list) for s in strs: key .join(sorted(s)) groups[key].append(s) return list(groups.values())核心就一个操作.join(sorted(s))。这里有个新手必踩的坑——sorted(s)返回的是字符列表比如[a, e, t]而列表在 Python 里不可哈希没法直接当字典的键必须先join成字符串。很多人在白板上写key sorted(s)一运行就报TypeError: unhashable type: list然后整个人懵掉。如果面试官要求你写其他语言思路完全一致。Java 版用char[]排序后new String即可public ListListString groupAnagrams(String[] strs) { MapString, ListString map new HashMap(); for (String s : strs) { char[] chars s.toCharArray(); Arrays.sort(chars); String key new String(chars); map.computeIfAbsent(key, k - new ArrayList()).add(s); } return new ArrayList(map.values()); }这段代码同样简洁核心也是“排序产生签名”。注意 Java 里Arrays.sort是对字符数组原地排序排序结果转回字符串时用new String(chars)而不是chars.toString()后者拿到的只是对象地址字符串这是另一个高频低级错误。2.2 复杂度分析与排序的代价设一共有n个字符串每个字符串平均长度是k。对单个字符串排序的时间复杂度是O(k log k)最坏情况下所有字符串都处理一遍总时间复杂度就是O(n * k log k)。空间上哈希表每个键平均长度为k每个原字符串都要存进结果因此空间复杂度是O(n * k)。这里有一个容易被面试官追问的细节字符串排序比较两个字符并不是 O(1) 吗为什么单个字符串排序是O(k log k)而不是O(k)因为基于比较的排序需要执行k log k次字符比较每次比较才 O(1)所以总代价确实是O(k log k)。如果继续较真Python 的 Timsort 在部分有序输入上会更快但平均意义下就是这个复杂度。排序法最大的优点是好写、好读、不容易出错。面试时作为首个方案非常合适因为你可以迅速写出干净代码再把剩余时间用在方案演进上。它的缺点是当k很大时排序开销会明显放大。假设有 10000 个长度 1000 的字符串10000 * 1000 * log2(1000)大约是 1 亿次级别操作计数法会更有优势。但如果只是普通英文单词k通常在 5 到 10 之间排序法的常数小实际跑起来并不慢。所以面试里说“排序法在短单词场景下足够好”不是借口是事实。3. 解法二字符计数表当哈希键理论上更优3.1 用 26 位频率数组给字符串“指纹”既然异位词的核心不变量是“每个字母出现次数”那就可以不排序直接统计频次。小写字母只有 26 个开一个长度 26 的整数数组遍历字符串每遇到一个字符就在对应位置加 1。统计完成后把这个数组转成不可变的哈希键。from collections import defaultdict def group_anagrams(strs): groups defaultdict(list) for s in strs: count [0] * 26 for ch in s: count[ord(ch) - ord(a)] 1 groups[tuple(count)].append(s) return list(groups.values())这里的关键是tuple(count)。列表count本身可变且不可哈希但转成元组之后内容相同的元组在 Python 中是相等的也会得到相同的哈希值。比如eat和tea统计出来的都是(1, 0, 0, 0, 1, ..., 1)位置 0 是a位置 4 是e位置 19 是t因此会进入同一个桶。Java 版通常不用 List 做键而是拼成一个带分隔符的字符串避免歧义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 c : count) { sb.append(#); sb.append(c); } map.computeIfAbsent(sb.toString(), k - new ArrayList()).add(s); } return new ArrayList(map.values()); }拼接时加#是为了防止连续数字串歧义。如果不加分隔符[1, 12]和[11, 2]都会拼成112导致两个不同的频次表撞到同一个键这属于工程实现里极高的低级错误但白板题里很容易被忽略。3.2 边界条件与实现细节空字符串的统计数组是全 0tuple([0] * 26)作为键所有空字符串自然归为一组。这一点比排序法更隐式——排序法里作为键也正常但如果你用某些语言写排序字符串空串排序后还是空串不会出错只是面试的时候要记得提一句“空字符串也能正常分组”体现边界意识。如果输入包含大写字母ord(ch) - ord(a)会算出负数或超过 25 的下标直接越界。工程中一般先做规范化s s.lower()如果字符集不是 26 个英文字母而是包含数字、空格、中文、表情符号固定数组就不够用了。更通用的做法是用collections.Counterfrom collections import Counter def group_anagrams(strs): groups defaultdict(list) for s in strs: counter Counter(s) key frozenset(counter.items()) groups[key].append(s) return list(groups.values())Counter本身不可哈希但frozenset(counter.items())把键值对冻结成集合就可以作为哈希键。要注意的是frozenset不区分字母顺序同一字符频次会合并正好符合需求。这个方案在处理中文时也同样适用比如“你好”和“好你”会被分到同一组。但是在真实中文语境里词序变化经常导致语义改变是否要按异位词聚类取决于业务目标这一点第 7 节会展开。计数法的时间复杂度是O(n * k)因为每个字符串只需遍历一次统计频次再固定遍历 26 个位置生成键总代价是O(n * (k 26))按大 O 记法就是O(n * k)。空间上每个键的长度固定为 26整体依然是O(n * k)。相比排序法它把log k换成了常数的 26在超长字符串场景下优势明显。4. 解法三质数乘积与更多奇技淫巧能聊但不能当主答案4.1 质数映射的思路用质数乘积给异位词做哈希是面试里很有意思的“加分项”。思路是把 26 个小写字母分别映射到一个质数比如a - 2, b - 3, c - 5, d - 7, e - 11依此类推。然后一个字符串的签名就是所有字符对应质数的乘积。由于质因数分解的唯一性两个字符串乘积相同当且仅当它们包含的字母及频次完全相同。from collections import defaultdict PRIMES [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101] def group_anagrams(strs): groups defaultdict(list) for s in strs: product 1 for ch in s: product * PRIMES[ord(ch) - ord(a)] groups[product].append(s) return list(groups.values())数学上非常优美乘法满足交换律所以字母顺序不影响结果。而且不需要再处理字符数组排序、也不需要生成 26 个数字的序列代码看起来甚至比前两种更短。空字符串的乘积是 1多个空字符串会归组行为正确。4.2 为什么工作里不推荐但你要是真把这套方案写到生产代码里我会劝你三思。第一个问题是溢出字符串稍微长一点比如 40 个字母乘积就可能达到几十位数字。Python 的大整数能扛住Java 的long会直接溢出必须换成BigInteger性能和内存双双恶化。第二个问题是可读性你没法从19399380这个键反推它代表什么字母组合将来排查数据问题根本不知道键长什么样。排序法和计数法生成的键要么让人一眼看懂要么可以快速转回频次表。所以质数乘积的正确用法是作为面试尾声的思维拓展彩蛋展示你理解哈希设计的数学本质。面试官问“还有没有别的思路”时提一嘴反而加分。主动拿它当主解法尤其是在 Java 面试里写BigInteger大概率会被继续追问溢出问题然后陷入不必要的解释。我在实际指导别人刷题时经常说一句话解题最优不一定等于面试最优面试最优也不一定等于工程最优这三个“最优”经常是三套选择。5. 三套方案对比与选型指南5.1 时间与空间复杂度汇总把前面三套方案放到同一张表里对比看起来更直观。方案时间复杂度空间复杂度哈希键形式工程友好度排序法O(n * k log k)O(n * k)变长字符串高键可读计数法O(n * k)O(n * k)定长元组/字符串中高需注意序列化质数乘积法O(n * k)O(n * k)整数乘积低溢出与可读性差这里有一个容易误解的空间复杂度三套方案的结果数组占了O(n * k)这部分无论如何都省不掉因为题目要求返回全部分组。哈希表本身存储键的额外开销则不同排序法的键平均长度为k计数法的键固定为 26质数法的键是一个大整数实际占用随字符串长度增长而增长。但在理论大 O 级别上三者都是O(n * k)所以面试时先答出这一层就够了。如果面试官追问“计数法理论上更快为什么你首选排序法”可以这样回答对于普通英文单词k很小log k几乎可以忽略排序法代码更简单、键更容易调试当数据中出现超长字符串时再切换到计数法。这种“根据输入特征选择方案”的思维方式比只背一种解法更能体现工程素养。5.2 不同数据形态下的选型建议在实际开发里选型不该只看算法复杂度还要看数据形态和排查成本。我给一个自己常用的决策规则输入是英文短语、商品标题、日志关键词长度基本不超过 50优先排序法。理由很简单出问题好查。你看到一个键是aet马上能想明白它来自eat但看到一个键是(1, 0, 0, ...)或19399380还得再转换一下。输入是 DNA 序列、基因片段、超长字符串长度可能上千优先计数法。排序一次 1000 字符的字符串代价明显比统计 26 个频次高。输入包含中文、多语言、emoji固定 26 维数组失效用Counter加frozenset的扩展方案。数据规模大到放不进单机内存上述所有单机方案都不够。需要走分布式框架比如 Spark 里对每个字符串生成签名后做groupBy(sign)本质上是排序法思想把“本地哈希表”换成了“分布式 Shuffle”。这时候算法本身没变瓶颈转移到了网络 IO 和倾斜 key 的处理上。这个决策规则我用了很多年最大的教训是不要为了理论上的一点性能提升牺牲可调试性。线上系统出问题能 5 分钟定位到键的含义比省那几毫秒重要得多。6. 刷题现场从笔试到面试的常见坑6.1 我踩过的五个经典坑先说我自己的黑历史。第一次写这题用的 Pythonkey sorted(s)直接当字典键报错后我盯着TypeError看了半分钟才反应过来要join。这种低级错误在面试高压环境下特别容易犯所以我现在教人一定会把“排序返回列表、列表不可哈希”这句话反复强调。第二个坑来自 Java。int[]数组在 Java 里是基于引用相等做哈希的直接拿数组当HashMap的键每组值都是 1。更隐蔽的是Arrays.asList(count)也不能用因为它是Listint[]里面元素还是数组。正确的做法是拼接为字符串或者用ListInteger转包装类。第三个坑是空字符串。很多人把if not s单独处理成一组但实际上多个空字符串都应该在同一组。正确的键是空串或者全 0 元组默认让它们自然归组即可不需要写分支。第四个坑是大规模重复字符串。比如输入是 10000 个abc排序法会对每个abc都排一遍。功能上没问题但如果你在追求极致性能可以在排序前查一下缓存或者先用Counter统计原字符串出现次数对去重后的字符串做分组最后再乘上次数生成结果。不过面试时并不需要主动做这个优化提一句“可以缓存高频键”就能体现思考深度。第五个坑是输入规范化。有些题解默认字符串只含小写字母但实际笔试里可能出现Eat和eat混在一起。我的习惯是写解法前先确认输入约束如果没说明就在代码开头加s s.lower()并去掉空格和标点如果要处理的话。这个动作本身不复杂却能避免大量边界问题。6.2 测试用例清单直接拿去用刷题时我习惯准备一组固定用例本地一跑能覆盖大部分边界。下面这份清单可以直接复制到你的测试文件里。输入数组预期分组情况覆盖点[][]空数组[][[]]单个空字符串[, ][[, ]]多个空字符串归组[a][[a]]单字符[ab, ba][[ab, ba]]最简异位词[abc, acb, bac][[abc, acb, bac]]三个异位词[abc, abd]两组各一个不同频次不归组[abc, abc, cba][[abc, abc, cba]]重复字符串[你好, 好你]一组若用 Counter 方案Unicode 字符我实际跑这些用例时发现最容易挂的是[, ]这一条。很多人会忘记空字符串也要分组或者手动用if s : return [[]]处理成错误结果。如果你写的排序法或计数法空字符串自然产生同一个键默认行为就是正确的不需要特判这反而说明“让不变量自然生效”比手动逻辑分支更可靠。7. 视角放大字母异位词分组在工程里的真身7.1 同义归一化与数据清洗字母异位词分组的底层思想是“签名归一化”。在真实业务里这个思想最常见的落点是数据清洗。举个例子跨境电商平台经常有卖家重复铺货把同一个商品标题里的词序打乱比如Organic Coconut Oil 500ml和Coconut Oil 500ml Organic平台如果不做处理搜索引擎会把它们当成两个不同的商品。处理流程和 LeetCode 题几乎一一对应先把标题统一转小写去掉标点符号把字符串内部字符排序或者按“单词”排序生成一个签名然后用这个签名做group by或reduce。按字符排序适合短文本按单词排序更适合英文标题因为它能保留词边界coconut oil和oil coconut会拿到同一个签名而ococonutil这种字符级签名没法再还原回可读文本。在数据库层面可以给表增加一列normalized_key写入时同步生成并建索引。后续查重直接用GROUP BY normalized_key HAVING COUNT(*) 1就能找出重复标题。这种冗余列方案最大的好处是查询走索引不需要对全表做实时计算。很多数据仓库建模里的“拉链表”“维度表”本质也是这种“增加规范化签名字段”的思路。7.2 文本指纹与风控场景另一个偏工程的方向是文本指纹。我在做风控相关需求时会用它识别批量变体文本。比如灰产用户为了绕过关键词屏蔽把“优惠券”写成“券优惠”把“进群加我”改成“加我进群”字面上是同一个字符集合字母异位词的签名完全一样可以直接作为召回特征。但这里要提醒一句字符重排并不等于语义相同尤其在中文场景。“北京欢迎你”和“你欢迎北京”是异位词但意思完全不同。如果直接按字母异位词分组去处罚用户误杀率一定很高。工程上正确做法是把它当作候选召回手段先用签名聚拢一批可能相关的文本再用真正的语义相似度模型做精排。我在实际项目里得到的比例大概是签名召回可以覆盖掉 70% 以上的恶意变体但最终确认违规还需要人工或模型复核。这个模式其实和解算法题很类似先用一个低成本的“不变量”把数据分桶再用更高成本但更准确的逻辑处理桶内内容。字母异位词分组就是那个低成本分桶器的教科书版本。理解了这层再看 LeetCode 题你不会只觉得它是“哈希表练习”而会看到一套可迁移的工程设计方法论。最后说点个人体会。刷这个题最有价值的收获不是背下某一种解法而是养成“寻找稳定签名”的思维习惯。我在实际代码里最常用的还是排序签名因为它让结果可读、可查、可解释只有当单条文本真的很长时才会换计数方案。如果你也写过类似的分组逻辑不管是处理商品标题还是识别文本变体欢迎在评论区说说你用的“签名方案”。下一题我准备聊聊 Top K 系列那个方向和大数据面试结合得更紧。