LeetCode49-字母异位词分组

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/group-anagrams/

中文链接：https://leetcode-cn.com/problems/group-anagrams/

题目详述

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

示例:

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

说明：

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

题目详解

  • 维护一个字母异位词的 id 映射到 List 的哈希表。
  • 每一个字符串添加到对应的 List 中。
  • 问题的关键在于对属于字母异位词的不同字符串怎么得到相同的 id。

方法一：

  • 对每个字符串进行排序，属于字母异位词的字符串会得到相同的字符串，可以把排序后的字符串作为 id。
  • 时间复杂度为 O(nLlogL)，n 为字符串的个数，L 为字符串的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class LeetCode_00049 {

    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs.length == 0) {
            return new ArrayList<>();
        }
        Map<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            char[] cs = s.toCharArray();
            Arrays.sort(cs);
            String key = String.valueOf(cs);
            if (!map.containsKey(key)) {
                map.put(key, new ArrayList<>());
            }
            map.get(key).add(s);
        }
        return new ArrayList<>(map.values());
    }
}

方法二：

  • 统计每个字符串各个字符出现的次数，计数相同的字符串才是字母异位词。
  • 为了得到一个便于比较的 id，可以将统计结果序列化。
  • 序列化采用的方式是 # 后紧跟的是字符出现的次数，得到的字符串作为 id。
  • 时间复杂度为 O(nL)，n 为字符串的个数，L 为字符串的长度。
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
public class LeetCode_00049 {

    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs.length == 0) {
            return new ArrayList<>();
        }
        Map<String, List<String>> map = new HashMap<>();
        for (String s : strs) {
            String id = getID(s);
            if (!map.containsKey(id)) {
                map.put(id, new ArrayList<>());
            }
            map.get(id).add(s);
        }
        return new ArrayList<>(map.values());
    }

    private String getID(String s) {
        int[] cnt = new int[26];
        for (char c : s.toCharArray()) {
            ++cnt[c - 'a'];
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 26; ++i) {
            sb.append('#').append(cnt[i]);
        }
        return sb.toString();
    }
}

方法三：

  • 可以用 Arrays.hashCode() 得到统计数组的 hashCode，把这个 hashCode 作为 id。
  • 时间复杂度为 O(nL)，n 为字符串的个数，L 为字符串的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class LeetCode_00049 {

    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs.length == 0) {
            return new ArrayList<>();
        }
        Map<Integer, List<String>> map = new HashMap<>();
        for (String s : strs) {
            int id = getID(s);
            List<String> list = map.computeIfAbsent(id, k -> new ArrayList<>());
            list.add(s);
        }
        return new ArrayList<>(map.values());
    }

    private int getID(String s) {
        int[] cnt = new int[26];
        for (char c : s.toCharArray()) {
            ++cnt[c - 'a'];
        }
        return Arrays.hashCode(cnt);
    }
}