49.Group Anagrams (Medium) Facebook Amazon Bloomberg Uber Yelp

Given an array of strings, group anagrams together.

For example, given:["eat", "tea", "tan", "ate", "nat", "bat"],
Return:

[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note: All inputs will be in lower-case.

Solution 1: HashMap + counting sort O(n * L); O(n)

Use HashMap, the key is the key string of anagrams, the value is the anagrams list.
Use counting sort to record each char's frequency and then generate the key of string.
Check if current string has same key string in HashMap, if has, add it to the corresponding anagrams list, otherwise, create a new list to store it.
At last, return the values of HashMap, which is the needed result.

    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs == null) {
            return null;
        }

        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] keyChar = new char[26]; //cannot use int to replace char
            for (int i = 0; i < str.length(); i++) {
                keyChar[str.charAt(i) - 'a']++;
            }
            //返回 char 数组参数的字符串表示形式。字符数组的内容已被复制，后续修改不会影响新创建的字符串。
            String keyStr = String.valueOf(keyChar);

//            int[] count = new int[26]; //cuz inputs are lowercase letters, we only need 26
//            for (int i = 0; i < str.length(); i++) {
//                count[str.charAt(i) - 'a']++;
//            }
//            String keyStr = "";//build a string key, eg."aabcccdd" -> 2a1b3c2d
//            for (int i = 0; i < count.length; i++) {
//                if (count[i] != 0) {
//                    keyStr += String.valueOf(count[i]) + String.valueOf((char) ('a' + i));
//                }
//            }

            if (!map.containsKey(keyStr)) {
                map.put(keyStr, new ArrayList<>());
            }
            map.get(keyStr).add(str);
        }
        return new ArrayList<>(map.values());
    }

Solution 2: HashMap + sort O(n * L * log L); O(n)

    public List<List<String>> groupAnagramsB(String[] strs) {
        if (strs == null) {
            return null;
        }

        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] c = str.toCharArray();
            Arrays.sort(c);
            String keyStr = String.valueOf(c);
            if (!map.containsKey(keyStr)) {
                map.put(keyStr, new ArrayList<>());
            }
            map.get(keyStr).add(str);
        }
//        res = (List)map.values(); // will lead to java.lang.ClassCastException
        return new ArrayList<>(map.values());
    }