LeetCode100之字母异位词分组(49)--Java

1.问题描述

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

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

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

难度等级

中等

题目链接

字母异位词分组

2.解题思路

题目要求我们将字母异位词进行分组，就是叫我们把相同的字母异位词放到同一List中，再把这些List放到一个List中返回(从返回值类型看出来的)。

 public List<List<String>> groupAnagrams(String[] strs)

那么，要把相同的字母异位词放到同一个List中，我们首先要解决的就是如何判断它们是否是相同的字母异位词。根据定义可以知道，如果我们将它们重新排序，可以得到一个相同的单词，那我们就可以把它们当做同一类的字母异位词。既然这样，我们可以把拿到的每一个字母异位词从小到大排序得到一个新的单词，如果它们得到的单词相等，那说明它们是同一组字母异位词。

   //将字符串的字符从小到大返回public String sortedStr(String str){//将字符串转化为数组char[] arr = str.toCharArray();//对数组进行排序Arrays.sort(arr);return new String(arr);}

核心的如果判断问题解决了，接下来，我们就要考虑如何把它们分到同一个组。我们从返回值类型看，它要返回的是List集合，但是我们从List集合是没办法判断List集合中的某一个字母异位词List集合是哪一类的。所以在我们寻找阶段，不能直接使用List集合来存储这些分组。这里我们可以使用key-value的结构来存储这些分组，key就是字母异位词从小到大排序得到的那个新单词，value就是分组List集合，这样一来，hashMap就是我们应该使用的存储数据结构了。

         //用一个map来存放已经比较过的词Map<String,List<String>> map = new HashMap<>();

接下来，我们只需要遍历字符串数组，将每一个字母异位词都取出来进行排序，然后根据排序后的单词从hashMap中取出对应的分组，将原字母异位词存入分组中即可，若hashMap中无该分组，则创建一个新的List集合，将字母异位词添加到新分组中，并把分组存入hashMap集合即可。

         for(int i = 0;i < strs.length;i++){//将字符串重构后与map中的key比较String newStr = sortedStr(strs[i]);//从map中获取该异位词的分组，如果分组不存在，则创建一个新的分组List<String> strList = map.getOrDefault(newStr,new ArrayList<String>());//将这个字符串加入分组中strList.add(strs[i]);//更新mapmap.put(newStr,strList);}

遍历完字符数组之后，我们所有的字母异位词分组就都在map集合中了，这时我们只需要把这些分组用一个for循环从map中取出来，存入的返回值要求的List集合即可。

          //将map中的list全部取出来List<List<String>> result = new ArrayList<>();for(Map.Entry<String,List<String>> entry:map.entrySet()){result.add(entry.getValue());}

3.代码展示

class Solution {public List<List<String>> groupAnagrams(String[] strs) {//用一个map来存放已经比较过的词Map<String,List<String>> map = new HashMap<>();for(int i = 0;i < strs.length;i++){//将字符串重构后与map中的key比较String newStr = sortedStr(strs[i]);//从map中获取该异位词的分组，如果分组不存在，则创建一个新的分组List<String> strList = map.getOrDefault(newStr,new ArrayList<String>());//将这个字符串加入分组中strList.add(strs[i]);//更新mapmap.put(newStr,strList);}//将map中的list全部取出来List<List<String>> result = new ArrayList<>();for(Map.Entry<String,List<String>> entry:map.entrySet()){result.add(entry.getValue());}return result;}//将字符串的字符从小到大返回public String sortedStr(String str){//将字符串转化为数组char[] arr = str.toCharArray();//对数组进行排序Arrays.sort(arr);return new String(arr);}
}