LeetCode 49字母异位词分组Python解法的时间复杂度分析

给定字符串数组strs，将字母异位词分组，返回结果顺序不限。字母异位词指由另一个单词/短语的字母重新排列形成的单词/短语，且使用全部原字母各一次。

我的Python解法 #

from typing import List

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anagrams = dict()   # 存储异位词的字典，值为列表

        for s in strs:
            sorted_st = sorted(s) # 对字符串字符排序
            sorted_str = ''.join(sorted_st) # 转换为字符串作为键

            if sorted_str in anagrams:              # 键已存在则追加当前字符串
                anagrams[sorted_str].append(s)     
            else:
                anagrams[sorted_str] = [s]        # 键不存在则创建新条目
                
        return list(anagrams.values())

时间复杂度分析 #

你的算法时间复杂度是O(n * k log k)，其中：

• n 是输入数组strs中字符串的总数
• k 是数组中最长字符串的长度

原因如下：

1. 外层需要遍历数组中的每一个字符串，这部分的时间开销是O(n)
2. 对每个字符串执行的sorted()操作，Python底层用的是Timsort算法，时间复杂度为O(k log k)（k为当前字符串长度）。后续的join操作是O(k)，相比排序的开销可以忽略不计
3. 字典的查找、追加操作平均时间复杂度为O(1)，不会影响整体的主导项

你提到的O(n)只是遍历的基础开销，但每个字符串的排序操作带来的O(k log k)是核心开销，无法忽略。整体复杂度由所有字符串的排序总开销决定，最坏情况下当所有字符串长度均为k时，总复杂度就是O(n*k log k)。

内容的提问来源于stack exchange，提问作者Arush Verma