字母异位词分组算法详解：从排序哈希到计数编码的工程选型-北京尧图网络

1. 题目深度拆解与思路选择字母异位词分组这道题我在面试和实际业务里都遇到过。先花两分钟把题目定义清楚给定一个字符串数组把由相同字母重新排列而成的单词放进同一组。比如[eat, tea, tan, ate, nat, bat]输出结果应该是[[bat], [nat, tan], [ate, eat, tea]]。字母异位词的本质是“字符构成相同但排列顺序不同”这意味着我们没法靠直接比较两个字符串是否相等来解决问题。从需求拆解来看这道题的核心难点其实就两个第一怎么高效判断两个词是不是异位词第二怎么把相同特征的词快速归拢到一起。前者考察的是对字符串编码方式的理解后者考察的是对哈希表应用场景的敏感度。就算换一种问法比如“给出一堆单词把回文词、字母异位词、变位词分组”底层逻辑都是一样的——先设计一个能代表“字符组成特征”的key再利用哈希表做聚合。我见过不少初学者拿到题目直接写双层循环两两比较是否为异位词时间复杂度瞬间变成 O(n² * m)n 是单词数量m 是单词长度。这种暴力解在数据量小的时候能过但面试官只要把字符串数组长度调大代码就彻底拉胯。所以这道题的关键不是“能不能做出来”而是“能不能用最优的时间复杂度做出来”。常见的解法有两条技术路线第一对每个单词内部做排序排序结果相同的就是异位词第二统计每个单词中 26 个字母的出现次数把次数序列作为特征。两条路线的本质其实一样都是把无序的字符集合映射成一个有序的、可比较的key区别只在映射方式。在实际面试或写业务代码时我一般先和对方确认一下字符范围。如果是纯小写英文字母解法可以做得非常极致如果包含大小写、数字、空格甚至 Unicode 字符那排序法反而更稳妥。这个判断很重要因为它直接决定了算法的时间复杂度和代码复杂度。我在下文会把排序法、计数法、以及一个工程上更稳健的编码方案全部展开讲一遍并给出每一步的取舍理由。2. 排序哈希法最简单直观的基准解法2.1 核心原理与代码实现排序哈希法的思路非常直接如果两个字符串互为字母异位词那么把它们内部的所有字符按字典序排序后得到的结果一定完全相同。比如eat排序后是aettea排序后也是aetate排序后还是aet于是这三个字符串就被映射到了同一个key下面。用Python实现的基准代码非常短核心逻辑就几行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())如果你不熟悉defaultdict也可以用普通字典加setdefault来实现不过defaultdict(list)确实能让代码干净不少。这里每一行都有明确的职责sorted(s)返回字符列表并排序.join(...)把字符列表重新拼成字符串groups[key].append(s)把原单词挂到对应的分组下。整个流程走完字典里每个key对应的value列表就是一个异位词组。Java版本也很常见面试中如果对方要求用Java写可以参考这个版本class Solution { 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()); } }2.2 时间复杂度与空间复杂度推导排序法的时间复杂度主要由两部分组成遍历所有字符串的 O(n)以及每次排序的 O(k log k)其中 k 是字符串的平均长度。所以总时间复杂度是 O(n * k log k)。如果字符串长度差异很大应该用最大长度 L 来估算也就是 O(n * L log L)。空间复杂度方面哈希表需要存储所有字符串所以是 O(n * k)。这里有个容易忽略的点排序过程本身也需要额外的栈空间不同语言对sorted的实现策略不一样Python 的 TimSort 最坏情况下需要 O(k) 的额外空间所以理论上额外空间是 O(n * k) 加上排序时的 O(k)但通常只记 O(n * k) 就够了。这个解法的优点是简单、直观、不容易写错而且不受字符集限制——不管你是小写字母、大写字母还是带数字和下划线的字符串排序后都能生成唯一的key天然支持多语言字符。缺点也很明显排序耗时较重在字符串很长的情况下排序开销会拖慢整体性能。举个例子一组包含 10 万个单词、每个单词平均 100 个字符的数据排序总耗时大概是 10万 * 100 * log100比后续的哈希查找高出一个数量级。所以在真实业务中如果数据量非常大我更推荐下面要讲的计数法——它把每次处理的成本从 O(k log k) 降到了 O(k)。3. 计数特征法更优的线性时间解法3.1 用字符计数数组做key既然每个字母异位词的字符组成相同那我们可以直接统计每个字符出现的次数。以 26 个小写字母为例维护一个长度为 26 的整数数组countcount[0]对应a的出现次数count[1]对应b的出现次数依此类推。两个字符串是否为异位词就看它们的count数组是否完全相等。但这里有一个关键问题count数组本身是可变的列表不能直接作为字典的key使用。所以我们需要把数组编码成一个不可变的对象。最简单的方式是把数组转成元组from collections import defaultdict def groupAnagrams(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())ord(ch) - ord(a)这一步把小写字母映射到 0 到 25 的索引位置。tuple(count)把列表转成元组后就可以作为字典的key使用了。这个解法的时间复杂度是 O(n * k)因为每个字符串只需要完整遍历一次没有排序环节。空间复杂度同样是 O(n * k)。你可能会问把长度为 26 的元组作为key哈希计算本身会不会有额外开销答案是会有但元组哈希的计算成本远低于排序的开销尤其在字符串长度越长时优势越明显。实测对随机单词列表做分组计数法通常比排序法快 1.5 到 3 倍。3.2 用字符串编码做keyJava版本的经典写法Java里元组不太好直接作为HashMap的key所以更常见的做法是把 count 数组拼成一个用分隔符隔开的字符串。比如aet出现 1 次c出现 2 次其他都是 0那把非空的字符和次数拼起来得到类似a1c2e1t1的特征串。但要注意必须包含所有 26 个字母的计数哪怕次数为 0 也要带上否则可能出现碰撞。Java 的经典解法是遍历 26 个字母把每个字母的计数和字符本身一起拼到 StringBuffer 里中间用#分隔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]; } StringBuilder sb new StringBuilder(); for (int i 0; i 26; i) { sb.append(#); sb.append(count[i]); } map.computeIfAbsent(sb.toString(), k - new ArrayList()).add(s); } return new ArrayList(map.values()); } }这段代码里sb.append(#)在最前面加了一个特殊字符作为分隔防止出现12和1 2这种歧义。比如若某字符计数是 12而下一个字符计数是 3那么不加分隔符会变成123可能和计数为 1、3 的另一个字符串产生的13发生语义混淆吗其实不会完全混淆因为长度固定但在拼接 key 时确保解析唯一性更安全。用#分隔后生成的 key 一定是一一对应的不会出现碰撞。3.3 计数编码的细节与注意事项使用计数法时有几个坑值得单独说明第一字符集大小。上面代码假设输入只包含 26 个小写英文字母。如果输入可能包含大写字母那么需要把 count 数组长度扩展到 52 或 128或者先统一转成小写再统计。如果包含数字、空格甚至中文这种基于固定字符集的计数方案就不够用了。处理方式有两种一是用collections.Counter(s)直接生成字符到次数的映射再对映射做规范化处理二是用广义的字符计数表长度设置为 256对应 ASCII。但如果是中文那就得往 Unicode 方向思考了。第二计数序列的哈希性能。在 Python 中tuple(count)作为 key 时每次计算哈希需要遍历整个元组也就是 26 个整数这个成本其实很低。但在 Java 中如果字符串长度很长、内容很多StringBuilder方式每次会生成一个很长的字符串内存成本不可忽视。如果追求极致性能可以直接把计数数组作为Multiset或自定义对象的 hashCode但这会显著增加代码复杂度在面试中通常不必要。第三空字符串的处理。空字符串的计数数组全是 0tuple 编码后是(0,0,...,0)排序后则是空字符串这两种方式都能正确处理空字符串。但要注意空字符串会和其他空字符串分到一组这在题目语义上是合理的。4. 性能对比与工程选型排序法还是计数法既然两种解法都能正确实现字母异位词分组那实际做技术选型的时候到底该怎么选我自己的判断标准很简单看字符集范围和数据规模。对比维度排序哈希法计数特征法时间复杂度O(n * k log k)O(n * k)空间复杂度O(n * k)O(n * k)字符集适配性任意字符集固定字符集扩展较麻烦代码复杂度低几行搞定中等需要处理编码逻辑优点简单通用、不易出错线性时间大量数据时更快缺点长字符串排序开销明显字符集扩展时要改代码做个直观的测试场景假设有一组英文单词平均长度 8 个字符数量 10 万个。排序法的核心耗时约 10万 * 8 * log2(8) 240 万次字符比较计数法耗时约 10万 * 8 80 万次字符统计。当字符串长度增长到 100 个字符时排序法的比较次数会飙升到 10万 * 100 * log2(100) ≈ 6640 万次而计数法只有 1000 万次差距会被进一步拉大。所以当字符串较长、字符集固定且明确时计数法是更优的选择。但如果场景是通用的海外内容处理平台输入可能包含英文、数字、符号、甚至表情符号那排序法的通用性更强因为它不需要提前知道字符集大小只需对字符做排序一切字符都能排序。在这种业务场景下我通常直接用排序法代码更少、踩坑更少。还有一个折中方案值得提用质数乘积做key。思路是给 26 个字母各自分配一个质数a2, b3, c5, d7...然后把字符串中每个字母对应的质数相乘作为 key。因为质数乘积的质因数分解是唯一的所以异位词的乘积一定相同。这个想法很巧妙但工程上有一个致命问题整数溢出。单词稍长一点乘积就会超过 64 位整数的表示范围而且不同单词的乘积可能发生碰撞在数学上不会但在整数运算的有限表示范围内会发生。所以如果要用质数乘积法建议只在字符集小、单词短的题目限定下使用工程场景要慎重。5. 变体花式考法从分组到更多场景字母异位词分组这道题衍生出来的变种非常多面试刷题时会遇到真实业务里也会遇到类似需求。我总结几个高频变体都能沿用上面的思路做扩展。第一种变体判断两个单词是否为字母异位词。这个最简单分别统计字符次数后比较即可或者排序后比较字符串相等。时间复杂度 O(k1 k2) 或 O(k1 log k1 k2 log k2)。第二种变体给定一个单词从大量备选单词中找出所有异位词。可以把备选单词全部预处理建立 key 到原单词列表的哈希索引然后在索引里精确查找。这种“预处理哈希索引”的模式非常适合搜索推荐系统里的相似词聚合场景。第三种变体找出字符串数组中包含字母异位词的所有分组但要求按每组内单词的字典序输出。这时可以在每个分组内调用一次sorted(group)总体复杂度增加不高但输出效果更符合产品预期。第四种变体不是简单的字母异位词而是“忽略大小写和空格”的异位词判断。这种在自然语言处理的文本清洗中很常见。处理思路是先把字符串转成小写去掉空格和标点再做字符统计。注意这类需求往往还要考虑历遍 Unicode 字符的情况直接用collections.Counter处理字符序列比较合适按固定 26 个字母扩展就不太行了。第五种变体找出“可以由给定单词的所有字母重排得到的最长单词”这其实是异位词的逆运算。核心思路是把目标单词和备选单词都规范化排序或计数然后判断备选单词排序后的字符是否能完整包含在目标单词的计数字典里属于“多重集子集”问题。这个在搜索框自动补全、拼写纠错里都有应用。6. 从刷题到工程真实场景中会踩的坑我早期做内容安全平台的敏感词聚合时就遇到过类似的散射问题同一个意思的不同写法内部字符顺序被打乱导致关键词规则完全匹配不上。后来我意识到这本质上就是字母异位词问题于是把敏感词表按字符计数编码建立索引然后再对用户输入做同样的归一化实现批量召回。这里有几个真实场景的工程坑值得写出来。第一个坑Unicode 规范化。中文和英文混合文本中有些字符有组合形式和预组合形式之分比如 é 可以由e 组合重音符号组成也可以直接是预组合字符。在做字符统计前最好先做 Unicode 规范化NFKC 或 NFD否则同一个词会因为编码方式不同而分到不同组。Python 里用到unicodedata.normalize这是一个容易忽略的细节。第二个坑空白字符和标点。真实文本往往带着换行符、空格、标点符号先把文本清洗规则定义清楚再统计。是删除所有非字母数字字符还是保留并计入特征这取决于业务目标。如果不做清洗hello!和hello就会被分到不同组。第三个坑大小写归一化。业务上通常会把用户输入的英文统一转成小写但在某些语种里大小写的规则并不完全是一一对应关系。比如德语ß在大写转换时会变成SS一个字符变两个字符处理时需要注意。如果业务涉及多语言字符统计前要做明确的 casefold 规则。第四个坑内存占用。当一个分组下的单词数量非常大时把全部原始字符串挂在内存里会带来不小的压力。如果系统只需要知道每个分组的数量那可以在建立索引时只计数、不存原文只对命中的分组再回表查原文。第五个坑不需要严格的分组而是需要“相似度模糊匹配”。比如由一个拼写错误导致的近似异位词用严格的分组算法就无能为力了。这类场景通常需要结合编辑距离、字梯或向量化匹配。我第一次做搜索推荐里的同义词挖掘时就是因为把问题想得太“严格”忽略了拼写容错导致召回率过低。后来改为先分组、组内再计算编辑距离方案才落地。我在实际工程中使用的通用函数大致长这样改造一下就能适配很多场景import unicodedata from collections import Counter def normalize_token(text: str) - str: # 1. 统一 Unicode 字符表示 text unicodedata.normalize(NFKC, text) # 2. 统一大小写 text text.casefold() # 3. 去掉空格和常见标点按需调整 cleaned .join(ch for ch in text if ch.isalnum()) return cleaned def anagram_key(text: str): cleaned normalize_token(text) counter Counter(cleaned) # 为了支持未知字符集直接用排序后的“字符次数”对做 key return tuple(sorted(counter.items()))这里返回的 key 既包含字符也包含次数并且使用Counter处理任意字符集。和排序法相比它多了一次计数统计但结果和字符集无关比单纯的.join(sorted(cleaned))在语义上更灵活——比如某些场景需要忽略重复字符那只要在这里做一点调整即可。7. 常见问题与排查技巧实录7.1 为什么我的计数法代码结果不对最常见的原因是字符索引算错了。比如用了ord(ch) - ord(A)处理小写字母那所有索引都会变成负数。另一种情况是字符串里混入了空格但统计时把空格也算进去了导致 key 出现偏差。排查方式很简单先打印每个字符串的 key看看相同的异位词是否对应相同的 key。7.2 为什么结果分组和题目示例不一样这可能是因为输出分组顺序的问题。哈希表不保证遍历顺序所以分组的先后顺序可能和期望的不同。在 LeetCode 上只要保证同一个异位词组内的单词正确即可顺序无所谓。但在某些严格比对的场景下需要先对分组结果做排序再输出或者对组内单词做排序。7.3 用质数乘积做key会不会有问题会。虽然数学上质数分解唯一但字符串稍长整数就会溢出或产生精度问题。如果一定要用可以用 Python 的大整数来规避溢出但性能会下降用 Java 的话就需要BigInteger代价更大。所以我的建议是质数乘积法只作为思维拓展去理解真要写代码还是排序法或计数法更稳妥。7.4 内存吃紧怎么办当数据量非常大时所有哈希 key 会占用不少内存。尤其是计数法拼出的长 key 字符串比排序后的字符串占的内存更大。优化手段包括用短整型数组编码替代长字符串、用元组直接做 key、或者用外部存储如 Redis Hash存索引只在需要时取出原数据。7.5 面试时被追问有没有更优解怎么办通常面试官问“还能不能优化”期待的是从排序法升级到计数法。你可以说清楚当前的时间复杂度是 O(n * k log k)计数后可以降到 O(n * k)但代价是字符集假设更强。如果继续追问可以补充质数乘积法和它的工程局限性以及多字节字符集下排序法的优势。把适用边界讲清楚比死背一个“最优解”更能体现工程思维。7.6 如果字符串数组为空代码会崩溃吗不会。遍历空列表时直接返回一个空列表defaultdict(list)和HashMap都能正常处理。这是边界条件不需要特殊防御但可以加一个if not strs: return []提前返回让语义更清晰。我个人踩过最大的一个坑是在业务系统中直接把“排序后字符串相等”当作唯一判断标准但忽略了大小写和全角半角差异导致中文和英文混合文本的召回率偏低。后来调整了标准化流程把normalize - casefold - 去标点 - 排序合并成一个幂等函数放在数据入口统一执行问题才彻底解决。这也是我想特别提醒的一点字母异位词分组在刷题环境里只需要考虑纯字符数组但在真实生产环境里数据清洗往往决定了算法的成败。如果你现在正在准备面试我建议把排序法和计数法都亲手写一遍把时间复杂度的推导过程写在注释里把空字符串和单字符串等边界用例跑一遍。如果你是在业务中遇到类似的文本聚合需求记得先明确字符范围和数据量再决定用哪种方案。别一上来就套模板先看清楚场景再说。

字母异位词分组算法详解：从排序哈希到计数编码的工程选型

相关推荐

SpringBoot+Flowable实现航空货运调度订单配送系统

齿轮传动设计全流程：从选型到强度校核的实用指南

PHP周刊2026W35 | PHP 8.6.0 Beta 1发布、Laravel 13.25全局暂停队列、NativePHP v4原生UI、Symfony 8.2密集冲刺

更多资讯

GEO核心战场：非图文内容与信息块覆盖如何决定AI引用率

AI销售助手不是取代销售，而是解放销售生产力

多模型路由四层架构全景：从工具侧到智能路由的成本优化指南

跨平台SSH客户端对比：Xterminal、Termius与MobaXterm怎么选？

Ubuntu 20.04无人机开发环境搭建：PX4+ROS2+Gazebo+QGC实战指南

51单片机真实硬件响应链路与调试能力培养

今日更新

在S3C2410上移植Nucleus RTOS：启动、驱动与实时性调优实战

2026年Turnitin降重降AI二合一红黑榜：能过和别碰

2026期刊投稿AI写作工具实测：6款打分谁更值得用

本周精选

超人会飞不算本事：系统稳定依赖清晰规则与边界设计

超人VS蜘蛛侠：拆解超级IP的影响力与传播方法论

基于CNN的调制信号识别：MATLAB实现时频图分类实战

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？