【LeetCode Top 100】49. Group Anagrams【Medium】【JAVA】

待我称王封你为后i 2021-09-21 00:16 294阅读 0赞

## 1. 题目 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70]

## 2. 题意 ##

对输入的N个字符串进行**分组**，分组的依据为：同组内的字符串拥有**相同的字母组合**，排列顺序可以不同。

## 3. 方法一 ##

### 3.1 思路 ###

分类可以想到的就是**Map**这个数据结构，可以通过特定的Key值，将不同的元素放入到不同的key下进行分类。而我们分类的`依据是字符串拥有相同的字符组合，但顺序可以不同`，那我们可以考虑将字符串字符组合的`调整顺序`，都是`升序排列`，得到的新字符串可以做为对应组的Key值。例如，对于"ate"和"eat"，对他们进行降序排列，都为"aet"，即他们将被归为一类。

这样子做的时间复杂度是多少呢？假设有N个字符串，每个字符串长度约为K，即我们需要遍历所有的字符串，即O(N)，同时，对于每个字符串我们需要一次排序，最佳的时间复杂度为O(KlogK)，因此总的时间复杂度约为`O(NKlogK)`。

### 3.2 代码 ###

public List<List<String>> groupAnagrams1(String[] strs) { 
            // 用于进行分类
            HashMap<String, List<String>> maps = new HashMap<>();
            // 用于存放结果
            List<List<String>> output = new ArrayList<>();
    
            // 遍历每个元素
            for (String s : strs
                    ) { 
                // 将每个字符串的元素进行排序，排序的结果作为分类的Key
                char[] chars = s.toCharArray();
                Arrays.sort(chars);
                String temp = new String(chars);
    
                // 根据Key进行分类
                if (!maps.containsKey(temp)) { 
                    List<String> list = new ArrayList<>();
                    list.add(s);
                    maps.put(temp, list);
                    output.add(list);
                } else { 
                    maps.get(temp).add(s);
                }
            }
            return output;
        }

## 4. 方法二 ##

### 4.1 思路 ###

对于思路一，我们的开销主要是两个地方，一个是遍历了所有字符串的O(N)，这一块的开销无法避免，那我们考虑对每个字符串进行排序的O(KlogK)进行优化。首先，优化排序算法有些困难，基本很难再明显提升，那我们考虑是否能不进行排序。我们分组的依据是拥有相同的字符组合，顺序可以不同，那我们也可以`计算每个字母出现的次数`，字母共计26种，可以穷尽，因此该方案可行。例如对于"ate"和"eat"，前者拥有1个"a"，1个"t"，1个"e"，后者拥有1个"e"，1个"a"，1个"t"，两者的字符串组合相同，即归入同一类。

对于时间复杂度，计数每个字母出现的次数，我们只需要遍历每个字符串一次，即当字符串长度为K时，时间复杂度为O(K)，因此总的时间复杂度为`O(NK)`，优于第一种思路。

### 4.2 代码 ###

public List<List<String>> groupAnagrams(String[] strs) { 
            HashMap<String, List<String>> maps = new HashMap<>();
            List<List<String>> output = new ArrayList<>();
            for (String s : strs
                    ) { 
                // 该Key值与上面的思路的获取方式不同
                String temp = getString(s);
                if (!maps.containsKey(temp)) { 
                    List<String> list = new ArrayList<>();
                    list.add(s);
                    maps.put(temp, list);
                    output.add(list);
                } else { 
                    maps.get(temp).add(s);
                }
            }
            return output;
        }
    
        // 计算字符串中各个字母出现的次数作为Key值
        private String getString(String s) { 
            char[] count = new char[26];
            for (char a : s.toCharArray()
                 ) { 
                count[a - 'a']++;
            }
            return new String(count);
        }

### 4.3 运行结果 ###

方法二的运行结果：  
![在这里插入图片描述][20191208010818482.png]  
方法一，Leetcode平台上运行结果为7ms，略高于思路二的5ms  
![在这里插入图片描述][20191208011021443.png]

## 5. 相关链接 ##

[本题代码的github链接][github]  
[其他 LeetCode 题目解析][LeetCode]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70]: /images/20210920/b8c76283fc264ff0b2d3b639ebe5b428.png
[20191208010818482.png]: /images/20210920/06a92a7588d742ac8e7dcc7d1fcb3c7d.png
[20191208011021443.png]: /images/20210920/e488bdbec4574428ae925f6e55b74c7c.png
[github]: https://github.com/Parallelline1996/Leetcode/blob/master/Problems/src/main/java/page1/N49_GroupAnagrams.java
[LeetCode]: https://blog.csdn.net/applying/category_9629399.html