49. Group Anagrams

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.

public List<List<String>> groupAnagrams(String[] strs) {
    List<List<String>> res = new LinkedList<>();
    HashMap<String, List<String>> map = new HashMap<>();

    for (String str: strs) {
        String key = convert(str);            
        if (map.containsKey(key)) {
            map.get(key).add(str);
        } else {
            List<String> list = new LinkedList<>();
            list.add(str);
            map.put(key, list);
        }
    }

    for (Map.Entry<String, List<String>> entry: map.entrySet()) {
        res.add(entry.getValue());
    }

    return res;
}

private String convert(String str) {
    char[] chars = str.toCharArray();
    Arrays.sort(chars);

    // return Arrays.toString(chars);  // "[a, e, t]"
    return new String(chars);          // "aet"
}

几点：

• str.toCharArray() convert str to char array
• Arrays.toString(array) convert array to "[item, item, ..., item]"
• constructor of String: new String(char[] array), new String(byte[] array), new String(String str)
• HashMap: values() => Collection<V>, 'keySet() => Set<K>'

Solution 2: Count Sort

m: size of strs array;
n: length of str

上面的题解为 O(m * n * logn)
下面的题解 Runtime 为 O(m * n * 26).

如果是针对单词，上面的题解会更好，因为单词的长度是 20 以内。如果是很长的字符串，下面的题解会更好。

private String convert(String str) {
    int[] count = new int[26];
    for (char c: str.toCharArray()) {
        int index = (int)(c - 'a');
        count[index]++;
    }

    StringBuilder builder = new StringBuilder();
    for (int i = 0; i < count.length; i++) {
        if (count[i] == 0) {
            continue;
        }
        builder.append(count[i]).append('a' + i);
    }

    return builder.toString();
}