题目链接

49. 字母异位词分组

解题思路

字母异位词包含相同的字符及相同的出现次数，因此将字符串的字符排序后，同一组字符串会得到完全相同的结果。

遍历每个字符串，将排序结果作为哈希表的键，原字符串加入对应的列表。遍历结束后，哈希表中的所有列表就是最终分组。

复杂度

设字符串数量为 n，单个字符串的最大长度为 k：

  • 时间复杂度：O(n × k log k)
  • 空间复杂度：O(n × k)

Java 解答

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String str: strs) {
            char[] arr = str.toCharArray();
            Arrays.sort(arr);
            String key = new String(arr);

            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values());
    }
}

复盘

本题的核心是为同一组字母异位词设计稳定且唯一的分组标识。排序后的字符串直观、可靠，代价是每个字符串都需要执行一次排序。