样例

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

思路

将 anagram 相同的单词归为一类, key = encode(str)
以 Map<encoded str, List of anagrams> 存储各类 anagram.
1. 将每个单词 sort后 得到的字符串作为 key
2. 遍历每个单词，counts 数组统计每个字符出现的个数, 之后将 counts 数组作为key

时间复杂度

1. $O (n * m)$
2. $O (n * mlogm)$

n: 单词个数
m: 最长单词的长度

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> res = new ArrayList<>();
        if (strs == null || strs.length == 0) {
            return res;
        }

        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            String key = getKeyCounting(str);
            // String key = getKeySort(str);
            if (!map.containsKey(key)) {
                map.put(key, new ArrayList<>());
            }
            map.get(key).add(str);
        }

        return new ArrayList(map.values());
    }
    //1. 统计各个字符在单词中出现的次数作为 key
    private String getKeyCounting(String str) {
        char[] counts = new char[26];
        char[] arr = str.toCharArray();
        for (char ch : arr) {
            counts[ch - 'a'] ++;
        }
        return String.valueOf(counts);
    }

    //2. 将每个单词 sort后 得到字符串作为 key
    private String getKeySort(String str) {
        char[] arr = str.toCharArray();
        Arrays.sort(arr);
        return Arrays.toString(arr);
    }
}