LeetCode Hot 100 49.字母异位词分组-171主机测评

LeetCode Hot 100 49.字母异位词分组

原题地址：49. 字母异位词分组 – 力扣（LeetCode）

我们可以借助HashMap，对字母异位词进行分组，我们需要将排序后的字符串，作为map中的key, 对当前遍历到的字符串进行排序，然后在map中查找是否有对应的key，存在，则将该数组元素存入到这个key对应的value中，达到分组的目的。

同时，对于第一次遍历到的字符串元素，map中还没有相对应的key，我们需要先将它存入到list中作为value，然后再和key一起存入到map中。

我们可以借助java中的Arrays.sort() 这个API ，对字符串进行排序，减少代码工作量，并且要注意的是，Arrays.sort() 只能接收字符数组参数。我们需要将，在字符串数组中遍历到的字符串元素转为字符数组，再作为参数传递到这个方法中。

为什么使用HashMap：

对于一些，需要使用到key这个索引来进行分组，或者判断，统计出现频率，并且根据key还要存储对应的value的数据结构，我们可以通过借助HashMap来实现我们的算法。

拓展知识：如何判断在算法题目中，是否需要使用哈希表（HashMap/HashSet）结构

1.我们需要将一种数据映射到另一种数据，或者根据某种规则将数据归类时。

2.题目数据量比较大（N > 10^4）,题目涉及统计出现频率或者快速查找某个元素是否存在时。

3.题目需要知道，“某个元素是否出现过”，不需要知道它出现的频率，或者不需要元素的索引时。

4.查找“两数之和” 或者 “差值为k的两个元素” ，“补数” 这类问题。

具体的实现代码如下：

class Solution {
public List<List<String>> groupAnagrams(String[] strs) {

//首先定义一个Map
Map<String, List<String>> map = new HashMap<>();
for(String s : strs){

//将数组中的字符串进行排序 — Arrays.sort()接收的是char[] 因此我们要将拿到的字符串s ,转换成char[]中的每一个元素
char[] chars = s.toCharArray(); //将字符串转为字符数组
Arrays.sort(chars);
String key = new String(chars); //将排序后的字符数组转换成字符串
//String key = String.valueOf(chars);的效果是一样的，valueOf底层是return new String(value)

//根据排序后的字符串作为key，并且判断map中是否包含这个key
if (map.containsKey(key)){
//存在对应的key,将排序前的字符串添加到这个key对应的value中
map.get(key).add(s);
}else{
//不存在对应的key
//先将字符串s添加到list中
List<String> list = new ArrayList<>();
list.add(s);
//再创建一个新的key，并创建一个value存入map
map.put(key, list);
}
}

//java 7+以后有了类型推断，我们可以省略构造函数左侧的泛型声明
//return new ArrayList<List<String>>(map.values());
return new ArrayList<>(map.values());

}
}

运行示例：

在这里插入图片描述

LeetCode Hot 100 49.字母异位词分组