49. Group Anagrams

Leetcode Hash Table String

Given an array of strings, group anagrams together.

Example:

Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note:

• All inputs will be in lowercase.
• The order of your output does not matter.

分析

一开始想到了最笨的方法，对于每个字符串，与其他字符串一一比对，如果是错位词，则加入到相应的List中。判断错位词详见LeetCode 242. Valid Anagram。可惜这种方法超时了。

public List<List<String>> groupAnagrams(String[] strs) {
    List<List<String>> res = new ArrayList<>();
    Map<String, Integer> map = new HashMap<>();
    boolean isFind;
    for (int i = 0; i < strs.length; i++) {
        isFind = false;
        for (String str: map.keySet()) {
            if (isAnagram(str, strs[i])) {
                res.get(map.get(str)).add(strs[i]);
                isFind = true;
                continue;
            }
        }
        if (!isFind) {
            res.add(new ArrayList<String>());
            res.get(res.size() - 1).add(strs[i]);
            map.put(strs[i], res.size() - 1);
        }
    }
    return res;
}

public boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;

    // 一共只有26个字母
    int[] count = new int[26];
    for (int i = 0; i < s.length(); i++) {
        count[s.charAt(i) - 'a']++;
        count[t.charAt(i) - 'a']--;
    }

    for (int num : count)
        if (num != 0) return false;

    return true;
}

上面的方法之所以慢，是因为需要一一比对。如果$n$非常大时，而且分组非常大时，时间复杂度接近于$O(n^2)$。所以用哈希表来判断错位词比较合适。因为判断错位词的方法一般有2种(LeetCode 242. Valid Anagram)：排序和分类计数。所以这里也可以应用这两种方法。

首先是排序的方法：

public List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List> map = new HashMap<>();
    for (String str : strs) {
        char[] c = str.toCharArray();
        Arrays.sort(c);
        String s = String.valueOf(c);
        if (map.containsKey(s)) map.get(s).add(str);
        else map.put(String.valueOf(s), new ArrayList<>(Collections.singletonList(str)));
    }

    return new ArrayList(map.values());
}

然后是分类计数的方法：

public List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List> map = new HashMap<>();
    for (String str : strs) {
        int[] nums = new int[26];
        for (char c : str.toCharArray())
            nums[c - 'a']++;
        StringBuilder sb = new StringBuilder();
        for (int num : nums)
            sb.append(num);

        String s = sb.toString();
        if (map.containsKey(s)) map.get(s).add(str);
        else map.put(String.valueOf(s), new ArrayList<>(Collections.singletonList(str)));
    }
    return new ArrayList(map.values());
}