LeetCode每日练习题---49.字母异位词分组

49.字母异位词分组

条件

已知： 字符串数组

目标： 将字母异位词组合在一起

思想（时间复杂度太高超时了）

我的想法是，双重遍历的暴力方法 ， 先对字符串数组中的元素进行遍历 ，第一层遍历，然后在第二层遍历中找与第一层遍历的元素是字母异位词的元素，对于第一层遍历要去重，我们可以用一个大字典包含好几个小字典，然后如果此次字符的字典在大字典中我们可以直接跳过。最后输出

classSolution:defgroupAnagrams(self,strs:List[str])->List[List[str]]:n=len(strs)used=[False]*n result=[]foriinrange(n):ifused[i]:continuecount_s={}forcinstrs[i]:count_s[c]=count_s.get(c,0)+1current_group=[strs[i]]used[i]=Trueforjinrange(i+1,n):ifused[j]:continuecount_t={}forcinstrs[j]:count_t[c]=count_t.get(c,0)+1ifcount_s==count_t:current_group.append(strs[j])used[j]=Trueresult.append(current_group)returnresult

思想（正确—官方答案）

由于字母异位词是区分大小写的，所以我们可以把字母进行排序，然后通过比较是否一致即可知道是否为字母异位词

具体代码

fromcollectionsimportdefaultdictfromtypingimportListclassSolution:defgroupAnagrams(self,strs:List[str])->List[List[str]]:ans=defaultdict(list)forsinstrs:count=[0]*26# 26个字母forcins:count[ord(c)-ord('a')]+=1# 列表不能当key，转成元组#tuple(count)即为一个key标记同一种字母异位，而相应的value则为一组组的字母异位词ans[tuple(count)].append(s)returnlist(ans.values())

补充知识

from collections import defaultdict：

​ 它是python自带的工具 ，用来创建一个更加聪明的字典

​ 普通字典：在遇到不存在的key时会报错

​ 而智能字典：在遇到不存在的key时，会自动创建空列表[]

ord：是python内置函数，作用是返回这个字符的ASCII码

tuple(): 是将列表转化为元组 ，让他能当字典的key

​ 列表[]：可变 →不能当字典 key

​ 元组()：不可变 →可以当字典 key

本文为新手代码训练记录，实现可能不够完善。若存在错误或有更优思路，欢迎各位大佬在评论区留言指正，一起学习进步！