数据结构篇-05：哈希表解决字母异位词分组

本文对应力扣高频100 ——49、字母异位词分组

---

哈希表最大的特点就是它可以把搜索元素的时间复杂度降到O(1)。这一题就是要我们找到 “字母异位词” 并把它们放在一起。

“字母异位词”就是同一个单词中字母的不同组合形式。判断“字母异位词”有两个视角：1、所含字母数量和种类相等的两个字符串数组互为“字母异位词”，当我们将其排序后，互为异位词的两个字符串应该是相同的；2、字母出现次数相同的两个字符串数组互为“字母异位词”，我们把其中字母出现的次数记录下来，形成的数组应该是相同的。

方法一：以重新排序后的字符串作为哈希表的key

思想：所含字母数量和种类相等的两个字符串数组互为“字母异位词”，当我们将其排序后，互为异位词的两个字符串应该是相同的

public class Solution{public List<List<Integer>> groupAnagrams(String[] strs){//如果字符串strs为空，则返回一个空的数组if(strs == null || str.length == 0){return new ArrayList<>();}Map<String,List<Integer>> map = new HashMap<>();//遍历每一个元素for(String str : strs){//将strs中的元素从String类型转为char类型，便于排序char[] charStr = str.toCharArray();//将转为 字符数组 的元素进行排序Arrays.sort(charStr);//将排序后的字符数组转回String类型，用于哈希比较String sortedStr = new String(charStr);//如果哈希表中不包含当前元素，就将其添加到哈希表中if(!map.containsKey(sortedStr)){map.put(sortedStr,new ArrayList<>());}//相反的，如果哈希表中包含该元素，就将其添加到对应key值的value值中//在本题中，value值是一个数组map.get(sortedStr).add(str);}//返回最终数组return new ArrayList<>(map.values());}
}

 方法二：以字符出现次数作为哈希表的键

思想：字母出现次数相同的两个字符串数组互为“字母异位词”，我们把其中字母出现的次数记录下来，形成的数组应该是相同的。

比如 “abc” 和 “bac” 互为字母异位词，在这两个字符串中，“a”、“b”、“c”各出现一次

public class Solution{public List<List<Integer>> groupAnagrams(String[] strs){Map<String,List<String>> map = new HashMap<>();//遍历字符串数组中的每一个元素for(String str : strs){//定义一个count数组用于记录每个字母出现次数int[] count = new int[26];//遍历元素中的每一个字母，并将其记录到数组中for(char c : str.toCharArray()){count[c - 'a']++;}//将数组转为String类型，便于放入哈希表String key = Arrays.toString(count);//获取哈希表value值中的list数组List<String> list = map.getOrDefault(key,new ArrayList<>());//将原始元素str放入listlist.add(str);//将字母出现次数作为哈希表的key值，list作为value值map.put(key,list);}//最后返回哈希表的valuereturn new ArrayList<>(map.values());}
}