Given an array of strings, group anagrams together.

For example, given: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],

Return:

1
2
3
4
5
[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note: All inputs will be in lower-case.

O(n m log m) time solution

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 Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs == null || strs.length < 1) return null;
        List<List<String>> result = new LinkedList<List<String>>();
        HashMap<String, List<String>> map = new HashMap<>(); // the key can also be the char counter array's hashcode
        
        for (String s : strs) {
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            String ana = new String(chars);
            if (map.containsKey(ana)) {
                map.get(ana).add(s);
            } else {
                LinkedList<String> anas = new LinkedList<>();
                anas.add(s);
                map.put(ana, anas);
            }
        }
        
        result.addAll(map.values());
        return result;
    }
}