LeetCode-49. 字母异位词分组

classSolution:defgroupAnagrams(self,strs:List[str])-List[List[str]]: LeetCode 49.字母异位词分组 :param strs: 输入字符串数组 :return: 二维列表异位词放在同一个子列表中 # defaultdict(list): 如果访问的key不存在自动生成该key赋值为空列表mpcollections.defaultdict(list)# 循环取出每一个待处理的字符串forstinstrs:# sorted(st): 将字符串拆解字符并排序返回字符list# .join(): 把排好序的字符列表重新合并成字符串用作字典的键# 例如 tea - sorted - [a,e,t] - aetkey.join(sorted(st))# 把原字符串添加进对应key的列表中相同key就分到同一组mp[key].append(st)# mp.values()是字典值的视图对象里面保存各个分组转为普通list返回结果returnlist(mp.values())时间复杂度O(nklogk)其中 n 是 strs 中的字符串的数量k 是 strs 中的字符串的的最大长度。需要遍历 n 个字符串对于每个字符串需要 O(klogk) 的时间进行排序以及 O(1) 的时间更新哈希表因此总时间复杂度是 O(nklogk)。空间复杂度O(nk)其中 n 是 strs 中的字符串的数量k 是 strs 中的字符串的的最大长度。需要用哈希表存储全部字符串。