LC 面试题 10.02. 变位词组

题目描述

这是 LeetCode 上的 面试题 10.02. 变位词组 ，难度为 中等。

编写一种方法，对字符串数组进行排序，将所有变位词组合在一起。变位词是指字母相同，但排列不同的字符串。

注意：本题相对原题稍作修改

示例:

1
2
3
4
5
6
7
8
输入: ["eat", "tea", "tan", "ate", "nat", "bat"],

输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

说明：

  • 所有输入均为小写字母。
  • 不考虑答案输出的顺序。

模拟 + 排序

一个朴素的想法是根据题意进行模拟，对每个字符串进行排序作为 key，从而实现相同的「变位词」对应同一个 key，使用哈希表进行统计即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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;
    }
}

  • 时间复杂度：$O(\sum_{i = 0}^{n - 1}ss[i].length * \log{ss[i].length})$
  • 空间复杂度：$O(\sum_{i = 0}^{n - 1}ss[i])$

模拟 + 计数

方法一无法做到线性，主要是存在对字符串进行排序的环节。

事实上，我们可以利用字符集大小有限作为切入点（只包含小写字母），使用一个大小为 $26$ 的数组进行计数，然后对计数后的数组统计值进行拼接，作为哈希表的 key，从而实现线性复杂度。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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;
    }
}

  • 时间复杂度：令 $n$ 为数组大小，$C$ 为字符集大小，固定为 $26$。整体复杂度为 $O(\sum_{i = 0}^{n - 1}ss[i].length + n * C)$，
  • 空间复杂度：$O(\sum_{i = 0}^{n - 1}ss[i])$

质数分解唯一性

事实上，我们还能使用「质数分解唯一性」性质，使用质数乘积代指某个「变位词」。

具体的，我们可以先使用 static 代码块（确保只会发生一次）打表最小的 $26$ 个质数（任意 $26$ 个都可以，使用小的，乘积溢出风险低一点），这 $26$ 个质数分别对应了 $26$ 个字母。

对于一个「变位词」而言，其对应的质数乘积必然相同。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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<Long, List<String>> map = new HashMap<>();
        for (String s : ss) {
            long 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 (long key : map.keySet()) ans.add(map.get(key));
        return ans;
    }
}

  • 时间复杂度：$O(\sum_{i = 0}^{n - 1}ss[i].length)$
  • 空间复杂度：$O(\sum_{i = 0}^{n - 1}ss[i])$

溢出说明

使用 long 仍然存在溢出风险，但使用“长度不受限制”的高精度哈希值实现是不现实的。

哈希值必须是有限值域内，才有意义。

换句话说，如果使用高精度的哈希值的话，我们是无法直接将两个哈希值进行异或判断结果是否为 $0$ 来得出哈希值是否相同的结论，而是需要使用 $O(Len)$ 的复杂度来判定哈希值是否相同。

因此，针对存在的哈希冲突问题，要么是解决冲突；要是使用与「字符串哈希」类似的做法，不处理溢出（相当于模 $2^{64}$），但这样会存在溢出次数不一样的值对应的哈希值相同的问题，只能说是一种期望冲突不发生的做法。

最后

这是我们「刷穿 LeetCode」系列文章的第 No.面试题 10.02 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。