全部题目来自力扣，这里只做学习的记录，内容中部分为AI生成，有不对的地方可以评论或者私信哦~~

49. 字母异位词分组

💡 算法思路

• 字母异位词的本质是：字符种类和字符个数相同，只是排列顺序不同。

• 例如 "eat" 和 "tea" 都由字符 'e', 'a', 't' 组成，因此属于同一组字母异位词。

• 我们可以对每个字符串进行排序，得到一个具有唯一性的排序字符串作为键（key）：

  • 例如："eat" → "aet"，"tea" → "aet"，因此它们可以归入同一组。

• 使用一个字典（defaultdict(list)）来存储分组结果：

  • 键（key）：排序后的字符串。

  • 值（value）：所有属于该组的原始字符串列表。

• 遍历整个字符串数组，将每个字符串按规则归类。

• 最后将字典中的所有值组成结果返回即可。

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        d = defaultdict(list)
        for s in strs:
            sorted_s = ''.join(sorted(s))  # 把 s 排序，作为哈希表的 key
            d[sorted_s].append(s)  # 排序后相同的字符串分到同一组
        return list(d.values())  # 哈希表的 value 保存分组后的结果

⏱️ 时间复杂度分析

设：

• n 是字符串数组 strs 的长度（即字符串的个数），

• k 是字符串的平均长度。

主要操作：

1. 排序操作：

   • 每个字符串 s 被 sorted(s) 排序，时间复杂度为 O(k log k)。

   • 总共 n 个字符串，因此排序部分的总时间复杂度为：O(n * k log k)。

2. 遍历操作：

   • 遍历 n 个字符串，每次访问和插入字典的操作都是常数级的，因此是 O(n)。

   • 由于在处理过程中字符串拼接（''.join(sorted_s)) 也需要 O(k)，可以认为每次遍历字符串操作的时间也是 O(k)，因此遍历和插入操作总计也是 O(n * k)，不过排序部分是主导的。

综合时间复杂度：

• O(n * k log k)

🧠 空间复杂度分析

1. 哈希表（字典）存储：

   • 所有的字符串都被分组保存下来，每个字符串的长度为 k，有 n 个字符串。

   • 因此字典中总共存储的字符数量为 n * k。

   • 空间复杂度为：O(n * k)

2. 中间变量（排序后的字符串）：

   • 每次排序操作都生成一个新的字符串 sorted_s，每个长度为 k，共 n 次。

   • 在 Python 中字符串是不可变的，因此每个 sorted_s 占据新空间，总共也是 O(n * k)。

总空间复杂度：

• O(n * k)