leetcode49字母异位词分组（String）

发表于 | 分类于

题目

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例

1
2
3
4
5
6
7
8
输入: ["eat", "tea", "tan", "ate", "nat", "bat"],

输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

说明

  • 所有输入均为小写字母。
  • 不考虑答案输出的顺序。

题解

方法一：先采用sort排序，将具有相同字符的不同字符串转化为同一个字符串，Map<String,Integer>中key存的是排序后的字符串，value存的是List<List>这个返回结果的索引。

例如：”eat”,”tea”。排序后都为“aet”，list:”eat”(加进去);HashMap: “aet”,0;res:[“eat”];下一次循环碰到”tea”,它排序后的结果也是“aet”，所以“tea”应该和eat放在一个list里面，我们先检查HashMap里面是否包含“aet”,包含则找到该list，把它加入，对应的代码为：res.get(map.get(s))；以此进行。

方法二：不排序，而是用一个Map<Character,Integer>这个结构来记录具有相同字符的字符串，方法二整体用两层hash，Map<Map<字母,次数>,List<单词>>这样一个结构。

代码

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public class solution {
    /**
     * 方法一
     * @param strs
     * @return
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> res =new ArrayList<>();
        if (strs==null||strs.length==0) return res;
        Map<String,Integer> map = new HashMap<>();
        for (String str:strs){
            char[] ch = str.toCharArray();
            Arrays.sort(ch);
            String s =new String(ch);
            if (map.containsKey(s)){
                List<String> list = res.get(map.get(s));
                list.add(str);
            }else {
                List<String> list = new ArrayList<>();
                list.add(str);
                map.put(s,res.size());
                res.add(list);
            }
        }
        return res;
    }

    /**
     * 方法二
     * @param strs
     * @return
     */
    public List<List<String>> groupAnagrams2(String[] strs){
        Map<Map<Character,Integer>,List<String>> map =new HashMap<>();
        for (String word:strs){
            Map<Character,Integer> freq = new HashMap<>();
            for (char c:word.toCharArray()){
                freq.put(c,freq.getOrDefault(c,0)+1);
            }
            List<String> anagrams = map.get(freq);
            if (anagrams==null){
                anagrams =new ArrayList<>();
            }
            anagrams.add(word);
            map.put(freq,anagrams);
        }
        List<List<String >> sol = new ArrayList<>();
        for (Map<Character,Integer> freq: map.keySet()){
            sol.add(map.get(freq));
        }
        return sol;
    }
}