字母异位词分组[中等]

优质博文：IT-BLOG-CN

一、题目

给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。字母异位词是由重新排列源单词的所有字母得到的一个新单词。

示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:
输入: strs = [""]
输出: [[""]]

示例 3:
输入: strs = ["a"]
输出: [["a"]]

1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i]仅包含小写字母

二、代码

【1】由于互为字母异位词的两个字符串包含的字母相同，因此两个字符串中的相同字母出现的次数一定是相同的，故可以将每个字母出现的次数使用字符串表示，作为哈希表的键。由于字符串只包含小写字母，因此对于每个字符串，可以使用长度为26的数组记录每个字母出现的次数。需要注意的是，在使用数组作为哈希表的键时，不同语言的支持程度不同，因此不同语言的实现方式也不同。

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // 思想：将包含字母相同的字符串，想办法整合成相同的字符串作为key，然后从map中获取，并存入列表中
        Map<String, List<String>> map = new HashMap();
        for (int i = 0; i < strs.length; i++) {
            // 创建一个26位的数组，根据字母的asc码-`a`作为下标
            int[] words = new int[26];
            // 遍历字符串，并使用数组进行计数
            for (int j = 0; j < strs[i].length(); j++) {
                words[strs[i].charAt(j) - 'a']++;
            }
            // 根据下标整合key
            String key = "";
            for(int j = 0; j < 26; j++) {
                if (words[j] > 0) {
                    key += String.valueOf((char)('a' + j)) + words[j];
                }
            }
            List<String> wordList = map.getOrDefault(key, new ArrayList<String>());
            wordList.add(strs[i]);
            map.put(key, wordList);
        }
        return new ArrayList<List<String>>(map.values());
    }
}
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

时间复杂度： O(n(k+∣Σ∣))，其中n是strs中的字符串的数量，k是strs中的字符串的的最大长度，Σ是字符集，在本题中字符集为所有小写字母，∣Σ∣=26。需要遍历n个字符串，对于每个字符串，需要O(k)的时间计算每个字母出现的次数，O(∣Σ∣)的时间生成哈希表的键，以及O(1)的时间更新哈希表，因此总时间复杂度是O(n(k+∣Σ∣))。

空间复杂度： O(n(k+∣Σ∣))，其中n是strs中的字符串的数量，k是strs中的字符串的最大长度，Σ是字符集，在本题中字符集为所有小写字母，∣Σ∣=26。需要用哈希表存储全部字符串，而记录每个字符串中每个字母出现次数的数组需要的空间为O(∣Σ∣)，在渐进意义下小于O(n(k+∣Σ∣))，可以忽略不计。

【2】排序： 由于互为字母异位词的两个字符串包含的字母相同，因此对两个字符串分别进行排序之后得到的字符串一定是相同的，故可以将排序之后的字符串作为哈希表的键。

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // 思想：对字符串进行排序
        Map<String, List<String>> map = new HashMap();
        for (String str: strs) {
            // 对字符串进行排序【解题的重点】
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            List<String> wordList = map.getOrDefault(key, new ArrayList<String>());
            wordList.add(str);
            map.put(key, wordList);
        }
        return new ArrayList<List<String>>(map.values());
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

时间复杂度： O(nklog⁡k)，其中n是strs中的字符串的数量，k是strs中的字符串的的最大长度。需要遍历n个字符串，对于每个字符串，需要O(klog⁡k)的时间进行排序以及O(1)的时间更新哈希表，因此总时间复杂度是O(nklog⁡k)。
空间复杂度： O(nk)，其中n是strs中的字符串的数量，k是strs中的字符串的的最大长度。需要用哈希表存储全部字符串。