LeetCode-中级算法_leetcode 中级

字谜分组

时间： 2019-12-25

给定一个字符串数组，将字母异位词组合在一起。
字母异位词指字母相同，但排列不同的字符串。
示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]
说明：
所有输入均为小写字母。
不考虑答案输出的顺序。
1
2
3
4
5
6
7
8
9
10
11
12
13

思路：
1,字母异位词重新排序，会得到相同的结果，所以重新排序可以判断两个字符串是否互为字母异位词。
2,由于字母异位词重新排序后都会得到相同的字符串，所以我们可以定义一个 HashMap<String, List>，以排序后的字符串作为 key，然后将所有字母异位词保存到该 key 对应的 ArrayList 中。
3,最后再返回一个包含所有 ArrayList 的 List<List> 即可。
作者：Little丶Jerry

public List<List<String>> groupAnagrams(String[] strs) {
    HashMap<String, List<String>> hashMap = new HashMap<>();
    for (String str : strs) {
        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        String key = new String(chars);

        if (!hashMap.containsKey(key)) {
            hashMap.put(key, new ArrayList<>());
        }
        hashMap.get(key).add(str);
    }
    return new ArrayList<>(hashMap.values());
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14