[数据结构与算法]leetcode [49. 字母异位词分组](https: |leetcode-cn.com/problems/group-anagrams/)

leetcode 49. 字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

示例 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] 仅包含小写字母

Related Topics

哈希表

字符串

排序

总结：

使用哈希表来计算，有2种思路，对每一个单词排序，排序的结果作为键，同一组的单词排序后结果相同。

另一种思路，统计单词字母的数量，每一组的单词字母数量相同，将字母和数量拼接成字符串作为键。

思路1：排序

分析：字母异位词的意思就是一组单词中，有相同字母组成的单词分成一组。

思路：

每一组异位词都有一个共同点，那就是异位词的字母排序后顺序相同。

将排序后的结果作为共同点，作为哈希表的键，将一组字符串作为值。

• 遍历每一个字符串，得到字符数组排序，通过哈希确定在那一组。

class Solution {
 ? ?public List<List<String>> groupAnagrams(String[] strs) {
 ? ? ? ?Map<String,List<String>> map = new HashMap<>();
 ? ? ? ?for(int i = 0 ; i < strs.length;i++){
 ? ? ? ? ? ?char[] array = strs[i].toCharArray();
 ? ? ? ? ? ?Arrays.sort(array);
 ? ? ? ? ? ?//异位词排序后的结果一致  作为键
 ? ? ? ? ? ?String key = new String(array);
 ? ? ? ? ? ?//如果key存在 直接返回value 不存在直接添加
?
 ? ? ? ? ? ?if(map.containsKey(key)){
 ? ? ? ? ? ? ? ?map.get(key).add(strs[i]);
 ? ? ? ? ?  }else{
 ? ? ? ? ? ? ? ?List<String> list = new ArrayList<>();
 ? ? ? ? ? ? ? ?list.add(strs[i]);
 ? ? ? ? ? ? ? ?map.put(key,list);
 ? ? ? ? ?  }
 ? ? ?  }
 ? ? ? ?return new ArrayList<List<String>>(map.values());
 ?  }
?
}
解答成功:
            执行耗时:6 ms,击败了91.50% 的Java用户
            内存消耗:44.4 MB,击败了17.05% 的Java用户

思路2：计数

每一组单词中，单词的每个字母数量相同，将统计后数量大于0的字母按照字母+数量构成map中的键。

class Solution {
 ? ?public List<List<String>> groupAnagrams(String[] strs) {
?
 ? ? ? ?Map<String,List<String>> map = new HashMap<>();
 ? ? ? ?for(String str : strs){
 ? ? ? ? ? ?//统计单词字母数量
 ? ? ? ? ? ?int[] count = new int[26];
 ? ? ? ? ? ?int length = str.length();
 ? ? ? ? ? ?for(int i = 0 ; i < length;i++){
 ? ? ? ? ? ? ? ?count[str.charAt(i)-'a']++;
 ? ? ? ? ?  }
 ? ? ? ? ? ?//将字母和数量拼接成字符串
 ? ? ? ? ? ?StringBuilder sb = new StringBuilder();
 ? ? ? ? ? ?for(int i = 0 ; i < 26;i++){
 ? ? ? ? ? ? ? ?if(count[i]!=0){
 ? ? ? ? ? ? ? ? ? ?sb.append((char) (i+'a'));
 ? ? ? ? ? ? ? ? ? ?sb.append(count[i]);
 ? ? ? ? ? ? ?  }
 ? ? ? ? ?  }
 ? ? ? ? ? ?String key = sb.toString();//键
 ? ? ? ? ? ?List<String> list = map.getOrDefault(key,new ArrayList<String>());
 ? ? ? ? ? ?list.add(str);
 ? ? ? ? ? ?map.put(key,list);
 ? ? ?  }
 ? ? ? ?return new ArrayList<List<String>>(map.values());
 ?  }
}