题目描述
这是 LeetCode 上的 面试题 10.02. 变位词组 ，难度为 中等。
Tag : 「哈希表」、「排序」、「计数」、「数学」、「打表」
编写一种方法，对字符串数组进行排序，将所有变位词组合在一起。变位词是指字母相同，但排列不同的字符串。
注意：本题相对原题稍作修改
示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"], 输出: [ ["ate","eat","tea"], ["nat","tan"], ["bat"] ] 复制代码
说明：
- 所有输入均为小写字母。
- 不考虑答案输出的顺序。
模拟 + 排序
一个朴素的想法是根据题意进行模拟，对每个字符串进行排序作为 key，从而实现相同的「变位词」对应同一个 key，使用哈希表进行统计即可。
Java 代码：
class Solution { public List<List<String>> groupAnagrams(String[] ss) { List<List<String>> ans = new ArrayList<>(); Map<String, List<String>> map = new HashMap<>(); for (String s : ss) { char[] cs = s.toCharArray(); Arrays.sort(cs); String key = String.valueOf(cs); List<String> list = map.getOrDefault(key, new ArrayList<>()); list.add(s); map.put(key, list); } for (String key : map.keySet()) ans.add(map.get(key)); return ans; } } 复制代码
Python 3 代码：
class Solution: def groupAnagrams(self, strs: List[str]) -> List[List[str]]: ans = [] hashmap = defaultdict(list) for s in strs: key = "".join(sorted(s)) hashmap[key].append(s) for val in hashmap.values(): ans.append(val) return ans 复制代码
- 时间复杂度：O(\sum_{i = 0}^{n - 1}ss[i].length * \log{ss[i].length})O(∑i=0n−1ss[i].length∗logss[i].length)
- 空间复杂度：O(\sum_{i = 0}^{n - 1}ss[i])O(∑i=0n−1ss[i])
模拟 + 计数
方法一无法做到线性，主要是存在对字符串进行排序的环节。
事实上，我们可以利用字符集大小有限作为切入点（只包含小写字母），使用一个大小为 2626 的数组进行计数，然后对计数后的数组统计值进行拼接，作为哈希表的 key，从而实现线性复杂度。
Java 代码：
class Solution { public List<List<String>> groupAnagrams(String[] ss) { List<List<String>> ans = new ArrayList<>(); Map<String, List<String>> map = new HashMap<>(); for (String s : ss) { int[] cnts = new int[26]; for (char c : s.toCharArray()) cnts[c - 'a']++; StringBuilder sb = new StringBuilder(); for (int i : cnts) sb.append(i + "_"); String key = sb.toString(); List<String> list = map.getOrDefault(key, new ArrayList<>()); list.add(s); map.put(key, list); } for (String key : map.keySet()) ans.add(map.get(key)); return ans; } } 复制代码
Python 3 代码：
class Solution: def groupAnagrams(self, strs: List[str]) -> List[List[str]]: ans = [] hashmap = defaultdict(list) for s in strs: cnts = [0] * 26 for c in s: cnts[ord(c) - ord('a')] += 1 key = "_".join(map(str, cnts)) hashmap[key].append(s) for val in hashmap.values(): ans.append(val) return ans 复制代码
- 时间复杂度：令 nn 为数组大小，CC 为字符集大小，固定为 2626。整体复杂度为 O(\sum_{i = 0}^{n - 1}ss[i].length + n * C)O(∑i=0n−1ss[i].length+n∗C)，
- 空间复杂度：O(\sum_{i = 0}^{n - 1}ss[i])O(∑i=0n−1ss[i])
质数分解唯一性
事实上，我们还能使用「质数分解唯一性」性质，使用质数乘积代指某个「变位词」。
具体的，我们可以先使用 static 代码块（确保只会发生一次）打表最小的 2626 个质数（任意 2626 个都可以，使用小的，乘积溢出风险低一点），这 2626 个质数分别对应了 2626 个字母。
对于一个「变位词」而言，其对应的质数乘积必然相同。
Java 代码：
class Solution { static int[] nums = new int[26]; static { for (int i = 2, idx = 0; idx != 26; i++) { boolean ok = true; for (int j = 2; j <= i / j; j++) { if (i % j == 0) { ok = false; break; } } if (ok) nums[idx++] = i; } } public List<List<String>> groupAnagrams(String[] ss) { List<List<String>> ans = new ArrayList<>(); Map<Integer, List<String>> map = new HashMap<>(); for (String s : ss) { int cur = 1; for (char c : s.toCharArray()) { cur *= nums[c - 'a']; } List<String> list = map.getOrDefault(cur, new ArrayList<>()); list.add(s); map.put(cur, list); } for (int key : map.keySet()) ans.add(map.get(key)); return ans; } } 复制代码
Python 3 代码：
class Solution: nums = [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 groupAnagrams(self, strs: List[str]) -> List[List[str]]: ans = [] hashmap = defaultdict(list) for s in strs: cur = 1 for c in s: cur *= self.nums[ord(c) - 97] hashmap[cur].append(s) return list(hashmap.values()) 复制代码
- 时间复杂度：O(\sum_{i = 0}^{n - 1}ss[i].length)O(∑i=0n−1ss[i].length)
- 空间复杂度：O(\sum_{i = 0}^{n - 1}ss[i])O(∑i=0n−1ss[i])
溢出说明
使用 long 仍然存在溢出风险，但使用“长度不受限制”的高精度哈希值实现是不现实的。
哈希值必须是有限值域内，才有意义。
换句话说，如果使用高精度的哈希值的话，我们是无法直接将两个哈希值进行异或判断结果是否为 00 来得出哈希值是否相同的结论，而是需要使用 O(Len)O(Len) 的复杂度来判定哈希值是否相同。
因此，针对存在的哈希冲突问题，要么是解决冲突；要是使用与「字符串哈希」类似的做法，不处理溢出（相当于模 2^{64}264），但这样会存在溢出次数不一样的值对应的哈希值相同的问题，只能说是一种期望冲突不发生的做法。
最后
这是我们「刷穿 LeetCode」系列文章的第 No.面试题 10.02 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
