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

49.字母异位词分组条件已知 字符串数组目标 将字母异位词组合在一起思想时间复杂度太高超时了我的想法是双重遍历的暴力方法 先对字符串数组中的元素进行遍历 第一层遍历然后在第二层遍历中找与第一层遍历的元素是字母异位词的元素对于第一层遍历要去重我们可以用一个大字典包含好几个小字典然后如果此次字符的字典在大字典中我们可以直接跳过。最后输出classSolution:defgroupAnagrams(self,strs:List[str])-List[List[str]]:nlen(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(i1,n):ifused[j]:continuecount_t{}forcinstrs[j]:count_t[c]count_t.get(c,0)1ifcount_scount_t:current_group.append(strs[j])used[j]Trueresult.append(current_group)returnresult思想正确—官方答案由于字母异位词是区分大小写的所以我们可以把字母进行排序然后通过比较是否一致即可知道是否为字母异位词具体代码fromcollectionsimportdefaultdictfromtypingimportListclassSolution:defgroupAnagrams(self,strs:List[str])-List[List[str]]:ansdefaultdict(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本文为新手代码训练记录实现可能不够完善。若存在错误或有更优思路欢迎各位大佬在评论区留言指正一起学习进步