一、题目回顾
给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
示例 1:
输入:strs = ["eat", "tea", "tan", "ate", "nat", "bat"] 输出:[["bat"],["nat","tan"],["ate","eat","tea"]]
解释:
在 strs 中没有字符串可以通过重新排列来形成 'bat'。 字符串 'nat' 和 'tan' 是字母异位词,因为它们可以重新排列以形成彼此。 字符串 'ate' ,'eat' 和 'tea' 是字母异位词,因为它们可以重新排列以形成彼此。
示例 2:
输入:strs = [""] 输出:[[""]]
示例 3:
输入:strs = ["a"] 输出:[["a"]]
提示:
- 1 <= strs.length <= 10^4
- 0 <= strs[i].length <= 100
- strs[i] 仅包含小写字母
二、整体思路(用一个'统一标识'来分组)
如果两个字符串是字母异位词,那么把它们各自的字符按字母顺序排序后,得到的结果一定完全相同。 反过来,排序后相同的字符串,一定是字母异位词。
所以,我们可以:
- 对每个字符串,将其字符排序,得到它的'标准化形式'。
- 以这个标准化形式作为分组标识(key),把原始字符串放到对应的组里。
- 最后把所有的组取出来,就是答案。
三、预备知识
一开始做这道题的时候会很困惑,哈希表能不能实现一个键对多个值,难道我要创键好几个哈希表吗? 实际上不是'一个键对应多个值',而是'一个键对应一个列表,列表里可以存多个值'。
3.1 HashMap 的每个键永远只对应一个值
HashMap 本身不允许一个键直接映射到多个值,因为它的设计是 key → value 一对一。 但是我们可以通过让 value 成为一个集合(比如 List、Set)来达到逻辑上的'一对多'。
比如字母异位词分组这道题,我们可以用 Map<String, List>,key 是排序后的字符串,value 是 ArrayList,把同组的异位词都 add 到这个 list 里。
3.2 字符串与字符数组的转换
str.toCharArray( ):把字符串拆成一个个字符,放进 char[ ] 数组。 new String(char[ ]):把字符数组重新组合成一个新的字符串。
为什么不能直接用 str.sort()? 因为字符串是不可变的,没有 sort 方法,所以必须转成数组才能排序。
3.3 数组排序
Arrays.sort(char[ ]):对字符数组进行原地升序排序(会改变原数组)。 它是 Java 提供的快速排序实现,直接拿来用即可。
3.4 HashMap —— 键值对字典
Map<K, V> 是一个接口,HashMap 是其常用实现。 这里的泛型是 Map<String, List>,表示键是字符串,值是一个存放字符串的列表。
为什么值是 List? 因为一个标准化字符串(键)可能对应多个原始单词,必须用容器把它们都装起来。
3.5 getOrDefault —— 简化'取或建'
map.getOrDefault(key, defaultValue):
如果 key 存在,返回它对应的 value; 如果 key 不存在,返回 defaultValue(在这里是一个新创建的 ArrayList)。
这行代码替代了传统的 if (map.containsKey(key)) {…} else {…},非常简洁。

