算法升级之路（三）

字母异位词分组

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

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

示例 1:

输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]

解题思路
最容易想到的是：从第一个字符串开始，把字符串中的字符放入map中，然后循环比较每一个字符串的字符是不是在map中存在，
但是有几个问题难以解决

1. 查找出来的属于字母异位词的，没有办法去除，因为数组去除元素比较复杂
2. 占空间大，每一个字符串都要声明一个map来存

排序法：
字母异位词 他们包含的字符都是相等的，那经过排序之后的字符串也肯定相等，然后将他们放到map，最后将map中所有的value取到即可。

 public List<List<String>> groupAnagrams(String[] strs) {
        Map <String,List<String>> map = new HashMap <String,List<String>> ();
        if(strs.length==0){
            return new ArrayList<List<String>>();
        }
        List<List<String>> resList = new ArrayList();
        for(int i=0;i<strs.length;i++){
            char []array = strs[i].toCharArray();
            Arrays.sort(array);
            String key = new String (array);
            List<String> list=map.getOrDefault(key,new ArrayList<String>());
            list.add(strs[i]);
            map.put(key,list);     
            
        }
        return new ArrayList<List<String>>(map.values());

    }

在此种解法中学到的，
字符串转字符数组:char [] chars = str.toCharArray();
还有这个方法
map.getOrDefault(key,value);
如果key在map中不存在就，将value获取到
否则就获取map中key对应的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26