尧图建网站 尧图建网站 YAOTU WEB BUILD 免费咨询
ARTICLE DETAIL

资讯详情

深耕网站建设与建站编程的一线实战洞察。

字母异位词分组:哈希表核心应用与两种高效解法详解

字母异位词分组:哈希表核心应用与两种高效解法详解 1. 先搞清楚“字母异位词分组”到底在考什么如果你刚开始刷力扣LeetCode看到第49题“字母异位词分组”可能会有点懵。这题的核心不是让你去创造新算法而是让你把一个常见的编程直觉用代码高效、准确地实现出来。简单说题目给你一个字符串数组比如[eat, tea, tan, ate, nat, bat]。你需要把那些字母异位词就是字母种类和数量完全一样只是排列顺序不同的词分到同一组里。上面的例子最终输出应该是[[eat,tea,ate], [tan,nat], [bat]]。这题为什么重要因为它几乎是面试中“哈希表”应用的必考题。它不考你多复杂的算法思想就考两点第一你能不能想到用哈希表来建立映射关系第二你设计的“键”Key是否足够高效和准确。很多新手会卡在“如何设计这个键”上要么想复杂了要么有漏洞。所以这篇文章不光是讲通这道题我会带你拆解从暴力思路到最优解的完整思考路径重点是理解为什么哈希表加排序是标准解法以及在实际编码时有哪些细节坑比如字符串排序、哈希表键的选择需要避开。无论你是刚开始刷题的小白还是想巩固基础的老手都能从这里获得清晰的实操指南。2. 从最直接的“笨办法”开始想明确问题边界在接触任何算法题时我建议都先别急着想最优解。先用最符合直觉的“笨办法”把流程走通这能帮你彻底理解题目到底要你干什么边界条件是什么。对于这题最暴力的思路是这样的遍历数组中的每一个字符串。对于当前字符串再遍历数组中所有其他字符串。判断这两个字符串是否是字母异位词。如果是就把它们放到同一个组里。判断两个字符串是否为字母异位词也有个“笨办法”统计每个字母出现的次数。例如比较“eat”和“tea”我们会发现它们都有1个‘e’1个‘a’1个‘t’。这个暴力法的代码写出来会很冗长时间复杂度是 O(n² * m)其中 n 是字符串个数m 是字符串平均长度。当数据量稍大比如 n10000时完全不可行。但它的价值在于让我们明确了问题的核心操作如何快速判断两个字符串“本质”是否相同即字母组成是否一致。一旦明确了这点优化方向就清晰了我们需要一种方法能为“本质相同”的字符串生成一个唯一的、可比较的“签名”或“键”。这样判断操作就从两两比较变成了查找这个“键”是否已经存在。3. 核心突破为异位词设计一个唯一的“哈希键”哈希表Hash Table是解决这个问题的绝佳数据结构。它的核心思想是“键-值对”映射。我们可以把每个字符串计算出的“唯一签名”作为键Key把具有相同签名的字符串列表作为值Value。那么关键就在于如何设计这个“签名”。这里有两个最主流且高效的方法3.1 方法一排序字符串作为键这是最直观的方法。既然字母异位词排序后一定相同例如“eat”、“tea”、“ate”排序后都是“aet”那么排序后的字符串本身就是一个完美的唯一键。操作步骤创建一个哈希表map键是字符串值是一个字符串列表ListString。遍历输入的字符串数组。对于每个字符串s先将其转换为字符数组然后排序再转回字符串得到key。检查map中是否存在这个key如果不存在则以key为键新建一个列表并把原字符串s放进去。如果已存在则直接将原字符串s添加到该键对应的列表中。遍历结束后哈希表map中所有的值即那些列表就是最终答案。代码示例Javaimport java.util.*; class Solution { public ListListString groupAnagrams(String[] strs) { MapString, ListString map new HashMap(); for (String s : strs) { // 将字符串转换为字符数组并排序 char[] charArray s.toCharArray(); Arrays.sort(charArray); String key new String(charArray); // 根据排序后的key分组 map.putIfAbsent(key, new ArrayList()); map.get(key).add(s); } // 返回所有分组 return new ArrayList(map.values()); } }为什么这是标准解法思路清晰完美利用了字母异位词的定义。代码简洁逻辑一目了然不易出错。时间复杂度可接受遍历是 O(n)每个字符串排序是 O(m log m)总复杂度 O(n * m log m)。对于力扣的题目约束通常足够通过。3.2 方法二字母计数数组作为键排序法虽然好但字符串排序有一定开销。另一种更底层的方法是直接统计字母频率并用一个结构来表示这个计数。具体做法由于题目说明字符串只包含小写字母我们可以创建一个长度为26的整数数组count记录每个字母出现的次数。例如“eat”对应的数组是[1,0,0,...,1,...,1,...]a, e, t 位置为1。 然后我们需要将这个数组转换成一个可以当作哈希表键的东西。在Java中数组的hashCode()和equals()方法并不直接适用于作为基于内容的哈希键所以通常将其转换为一个格式固定的字符串比如“1#0#0#...1#...1#”用“#”分隔计数。操作步骤创建一个哈希表map键是表示计数的字符串值是字符串列表。遍历字符串数组。对每个字符串初始化一个长度为26的计数数组count遍历字符串的每个字符在对应位置增加计数。将count数组拼接成一个特定格式的字符串key例如用StringBuilder拼接数字间用“#”分隔。以key为键进行分组操作同方法一。代码示例Javaclass 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 num : count) { sb.append(#); sb.append(num); } String key sb.toString(); map.putIfAbsent(key, new ArrayList()); map.get(key).add(s); } return new ArrayList(map.values()); } }两种方法对比与选择特性排序法计数法核心思想异位词排序后相同异位词字母频率相同键的生成Arrays.sort(charArray)遍历统计拼接字符串时间复杂度O(n * m log m)O(n * m)空间复杂度O(n * m)O(n * m)优点代码极其简洁逻辑直观理论上时间复杂度更低尤其当 m 较大时缺点排序有额外开销键的生成和比较稍复杂代码长一些适用场景字符串平均长度 m 较小或追求代码简洁字符串平均长度 m 较大对性能有极致要求对于面试和日常刷题我建议优先掌握排序法。因为它更直观在绝大多数情况下性能足够且代码出错概率低。当你被面试官追问“还有没有其他方法”或“如何优化”时再提出计数法这会显得你思考有深度。4. 动手实现环境、步骤与避坑指南理解了原理我们来看看如何把它变成能运行的代码。这里以最通用的排序法为例用 Java 语言演示。4.1 环境与准备你只需要一个能运行 Java 的环境。可以是本地IDE如 IntelliJ IDEA, Eclipse, VS Code 安装 Java 扩展。在线编译器力扣LeetCode的题目页面本身就自带代码编辑器和运行环境这是最方便的。命令行确保安装了 JDK用javac编译java运行。在开始写代码前我习惯先明确输入输出。力扣已经定义好了函数签名class Solution { public ListListString groupAnagrams(String[] strs) { // 你的代码 } }输入是String[] strs输出是ListListString。这个输出类型意味着你要返回一个列表里面的每个元素又是一个字符串列表即一个分组。4.2 逐步实现与详解我们一步步把之前的思路翻译成代码并解释每个细节。第一步导入必要的包import java.util.*;需要用到HashMap,List,ArrayList,Arrays。第二步创建哈希表MapString, ListString map new HashMap();键Key是排序后的字符串String值Value是原始字符串组成的列表ListString。第三步遍历输入数组for (String s : strs) { // 处理每个字符串 s }第四步为每个字符串生成键这是核心操作也是最容易出错的地方。char[] charArray s.toCharArray(); // 1. 转成字符数组 Arrays.sort(charArray); // 2. 排序 String key new String(charArray); // 3. 转回字符串注意不要写成String key charArray.toString();这得不到你想要的字符串内容。第五步更新哈希表// 如果map中还没有这个key就放入一个空列表 map.putIfAbsent(key, new ArrayList()); // 然后将当前字符串s添加到这个key对应的列表中 map.get(key).add(s);这里使用putIfAbsent方法非常简洁它等价于if (!map.containsKey(key)) { map.put(key, new ArrayList()); } map.get(key).add(s);第六步返回结果return new ArrayList(map.values());map.values()返回的是所有分组列表的集合CollectionListString题目要求返回ListListString所以用new ArrayList(...)包装一下。4.3 常见“坑点”与排查即使思路正确代码也可能因为细节问题跑不通。下面是我在带新人刷题时他们最容易遇到的几个问题键生成错误如上所述错误地将字符数组charArray直接toString()。一定要用new String(charArray)。哈希表值类型错误MapString, ListString这里值必须是ListString而不是String。初学者有时会误以为值是单个字符串。返回类型不匹配函数签名要求返回ListListString。如果你直接return map.values();会报类型错误因为values()返回的是CollectionV。忽略空输入题目可能给出空数组[]。我们的代码能处理吗可以。map.values()会返回一个空集合new ArrayList(空集合)会得到一个空的ArrayList符合预期。性能疑虑有人担心排序开销大。在力扣的测试用例范围内这个开销是可接受的。如果真遇到超长字符串比如长度超过10^4可以优先考虑计数法。调试建议 当你觉得代码逻辑没错但结果不对时不要慌。在关键位置打印中间变量比如打印出每个字符串s和它对应的key。你会立刻发现是键生成错了还是分组逻辑错了。5. 从解题到掌握举一反三与进阶思考搞定一道题不能只满足于“通过”。要从中提炼出可复用的模式和思考框架。5.1 本题的通用模式“字母异位词分组”本质上是一个“归一化”“哈希聚合”的问题。归一化将不同表现形式但本质相同的对象映射到同一个标准形式如排序后的字符串、计数数组字符串。哈希聚合以这个标准形式为键利用哈希表进行快速归类。很多问题都符合这个模式。例如力扣 242. 有效的字母异位词本题的简化版判断两个字符串是否异位词本质上就是比较它们的“归一化”结果是否相等。对具有相同特征的对象进行分组比如有一批交易记录需要按“交易类型日期”分组统计总额。“交易类型日期”就是你的“键”。5.2 如果字符串包含 Unicode 字符怎么办题目假设只包含小写字母所以我们的计数数组长度是26。如果字符串可以包含任何 Unicode 字符计数法还能用吗可以但数据结构要变。我们不能再用固定长度的数组了因为 Unicode 字符范围太大。这时有两种选择继续使用排序法Arrays.sort(charArray)依然有效这是最省事的通用解法。使用HashMapCharacter, Integer作为计数器用另一个哈希表来统计频率然后将这个频率哈希表的内容序列化成一个字符串作为键例如按字符编码排序后拼接。但这比排序法更复杂在面试中如果面试官不特别要求直接说用排序法处理通用情况即可。5.3 如何在其他语言中实现思路完全一致只是语法不同。Python 示例排序法class Solution: def groupAnagrams(self, strs: List[str]) - List[List[str]]: from collections import defaultdict ans defaultdict(list) for s in strs: key .join(sorted(s)) # Python中排序字符串很方便 ans[key].append(s) return list(ans.values())Python 的defaultdict和sorted函数让代码非常简洁。C 示例排序法class Solution { public: vectorvectorstring groupAnagrams(vectorstring strs) { unordered_mapstring, vectorstring mp; for (string s : strs) { string key s; sort(key.begin(), key.end()); mp[key].push_back(s); } vectorvectorstring ans; for (auto p : mp) { ans.push_back(p.second); } return ans; } };5.4 关于“力扣热题100”和刷题策略“字母异位词分组”是“力扣热题100”中的一道经典题。把它刷透意义远大于刷十道模糊的题。我的建议是第一遍理解并写出代码用你最熟悉的语言按照本文的步骤自己实现一遍排序法确保通过。第二遍尝试其他方法在不看答案的情况下尝试实现计数法。对比两种方法的代码和性能感受。第三遍隔天复现关上所有参考资料从头到尾再写一遍。这能检验你是否真正掌握了思路而不是记住了代码。第四遍总结模式在笔记本或代码注释里写下这道题的核心思想“归一化哈希聚合”、关键步骤和易错点。按照这个节奏每吃透一道题你收获的是一类问题的解法而不仅仅是一个答案。哈希表相关的题目如两数之和LeetCode 1、最长连续序列LeetCode 128等都可以用类似的“键值映射”思维去攻克。最后记住一个很实用的心态在面试或平时开发中当你遇到需要“归类”或“找相同”的问题时先问问自己——“我能不能为这些东西设计一个唯一的‘键’”如果能哈希表很可能就是你的解决方案。这道“字母异位词分组”题就是训练这种思维的最佳起点。
返回列表