49. 字母异位词分组

字母计数法

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs == null || strs.length == 0) {
            return new ArrayList<>();
        }
        Map<String, List<String>> map = new HashMap<>();
        int[] letters = new int[26];
        for (String str : strs) {
            Arrays.fill(letters, 0);
            for (int i = 0; i < str.length(); i++) {
                letters[str.charAt(i) - 'a']++;
            }
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 26; i++) {
                sb.append("#");
                sb.append(letters[i]);
            }
            String s = sb.toString();
            if (!map.containsKey(s)) {
                map.put(s, new ArrayList<>());
            }
            map.get(s).add(str); 
        }
        return new ArrayList<>(map.values());
    }
}

• 时间复杂度 O(NK)，其中N为数组的长度，而K为数组中字符串的最大长度
• 空间复杂度 O(NK)，其中N为数组的长度，而K为数组中字符串的最大长度

排序后比较

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs == null || strs.length == 0) {
            return new ArrayList<>();
        }
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] ch = str.toCharArray();
            Arrays.sort(ch);
            String s = String.valueOf(ch);
            if (!map.containsKey(s)) {
                map.put(s, new ArrayList<>());
            }
            map.get(s).add(str); 
        }
        return new ArrayList<>(map.values());
    }
}

• 时间复杂度 O(NK logK)，其中N为数组的长度，而K为数组中字符串的最大长度
• 空间复杂度 O(NK)，其中N为数组的长度，而K为数组中字符串的最大长度