📃 题目描述

题目链接：

• 剑指 Offer II 033. 变位词组 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)
• 49. 字母异位词分组 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

🔔 解题思路

上道题 剑指 Offer II 032. 有效的变位词 - 力扣（LeetCode） (leetcode-cn.com) (opens new window) 把相同的两个字符串不视为异位词，而本道题是把相同的两个字符串视为异位词的，小细节，注意下就行

思路：把一组变位词映射到同一个单词。

由于互为变位词的单词的字母出现的次数分别相同，因此如果把单词中的字母排序就会得到相同的字符串。例如，把"eat"、"tea"和"ate"的字母按照字母表顺序排序都得到字符串"aet"。

因此，可以定义一个哈希表，哈希表的 key 是把单词字母排序得到的字符串，而 value 为对应的一些变位词（通过排序后能够和 key 相同的字符串）：

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // key: 排序好的字符串，value: 通过排序后能够和 key 相同的字符串
        Map<String, List<String>> map = new HashMap<>();

        for (String str : strs) {
            char[] charArray = str.toCharArray();
            // 按照字母顺序排序
            Arrays.sort(charArray);
            String sorted = new String(charArray);
            map.putIfAbsent(sorted, new ArrayList<>());

            map.get(sorted).add(str);
        }

        List<List<String>> res = new ArrayList<>();
        for (String key : map.keySet()) {
            res.add(map.get(key));
        }

        return res;
    }
}

💥 复杂度分析

• 空间复杂度：O(N)
• 时间复杂度：主要就是循环和排序的时间：如果每个单词平均有 m 个字母，排序一个单词需要 O(mlogm) 的时间。假设总共有n个单词，该算法总的时间复杂度是O(nmlogm)