字母异位词分组[中等]

╰+攻爆jí腚メ 2024-02-17 08:31 7阅读 0赞

优质博文：[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());
        }
    }

**时间复杂度：** `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());
        }
    }

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

###  ###

[IT-BLOG-CN]: https://it-blog-cn.com/blogs/algorithm/topic/medium/letter_heterotopic.html