字母异位词分组

发表于
本文字数： 3k 阅读时长 ≈ 3 分钟

LeetCode每日一题，49. Group Anagrams

先看题目描述

rmxVF1.png

大意就是给定一个字符串数组，让我们将其中的字母异位词分组放在一起，字母异位词是指字母相同，但排列不同的字符串

算法和思路

排序+哈希表

由于互为字母异位词的两个字符串所含字母相同，那么对两个字符串排序后得到的字符串一定相同，于是可以选择排序后的字符串作为字母异位词标志，将其作为哈希表的键，哈希表的值就为其对应的字母异位词列表

遍历每个字符串，将该字符串排序得到字母异位词的标志，然后以其作为键得到哈希表中存储的字母异位词列表，然后将该字符串加入该异位词列表中，哈希表中每个键值对就是一个字母异位词标志和其对应的字母异位词列表。遍历完字符串后返回哈希表的 values 中存储的所有字母异位词列表即可

计数+哈希表

和上一种方法的思路是一致的，只是使用的字母异位词标志不同，该方法是将字符串中每个字母和其出现的次数用字符串表示，作为字母异位词标志，于是哈希表的键是字符串表示的每个字母和其出现次数，值是字母异位词标志对应的字母异位词列表

算法源码

排序+哈希表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] cs = str.toCharArray();
            Arrays.sort(cs);
            String key = new String(cs);
            List<String> list = map.getOrDefault(key, new ArrayList<>());
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<>(map.values());
    }
}

注意：哈希表中必须使用 String 作为 key，因为在内容相同的情况下，String 会 hash 得到相同的 key，而 char[] 由于机制特殊，相同的内容在 hash 后值不会相同

还有就是上面的代码中使用了 getOrDefault() 方法将 key 值存在和不存在的情况整合到了一起，但实际上 key 值存在时，由于 list 是个引用，最后是不需要执行 map.put(key, list) 的，只有当 key 值不存在时才需要执行该操作，因此实际上会执行大量没必要的 map.put() 操作，故可以将 key 值存在和不存在的情况分开考虑，这样可以节省时间，代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] cs = str.toCharArray();
            Arrays.sort(cs);
            String key = new String(cs);
            if (map.containsKey(key)) {
                List<String> list = map.get(key);
                list.add(str);
            } else {
                List<String> list = new ArrayList<>();
                list.add(str);
                map.put(key, list);
            }
        }
        return new ArrayList<>(map.values());
    }
}

计数+哈希表

和上一种算法的实现源码的区别主要就是哈希表的键不同，是将字符串中所有字母和其出现次数作为 key，实现代码如下，该代码同样可以将 key 存在和不存在的情况分开考虑，从而改善运行效率

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            int[] counts = new int[26];
            for (char c : str.toCharArray()) {
                counts[c - 'a']++;
            }
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 26; i++) {
                if (counts[i] > 0) {
                    sb.append((char)('a' + i));
                    sb.append(counts[i]);
                }
            }
            String key = sb.toString();
            List<String> list = map.getOrDefault(key, new ArrayList<>());
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<>(map.values());
    }
}