LeetCode49-GroupAnagrams

LeetCode49:GroupAnagramsGroupAnagrams题目：给定一个字符串数组，将这些字母组合在一起。字谜是一串具有相同字母但排列不同的字符。给定一个字符串数组，将字谜组合在一起。示例：输入：["eat","tea","tan","ate","nat","bat"]，输出：[["ate","eat","tea"],["nat","tan"],["bat"]]注：所有输入均为小写字母。不考虑答案输出的顺序。注意：所有输入均为小写。输出顺序无关紧要。解题思路：题目的要求是不管字母怎么排序，只要字母相同就归为一类，只要所有单词的字母按照一定的规则，只要每个单词的字母按照规则排列成同一个字符串，就会归为一类排序好的字母解题：使用哈希映射{Key:Value}Key是一个排序后的字符串，Value为数组，存放与Key相同字母的单词，遍历每个单词对字母进行排序，查找Keys中是否存在排序后的字符串，使用hashmap降低查找的时间复杂度运算复杂度为O(1)，求解逻辑为（这里按字母升序排列）：input:["eat","tea","tan","ate","nat","bat"]buildhashmapmap={}遍历字符串数组：第一个词："eat"-->"aet""aet"在map中不存在，创建映射{"aet":["eat"]}第二个词："tea"-->"aet""aet"存在于map中，加上它的Values{"aet":["eat","tea"]}第三个词:"tan"-->"ant""ant"在映射中不存在，创建一个映射{"aet":["eat","tea"];"ant":["tan"]}第四个词："ate"-->"aet""aet"存在于map中，添加其Values{"aet":["eat","tea",“吃”];"ant":["tan"]}......map={"aet":["eat","tea","ate"];“蚂蚁”：[“棕褐色”，“自然”]；"abt":["bat"]}返回散列映射的值数组：[["ate","eat","tea"],["nat","tan"],["bat"]]复杂度：时间复杂度：O(N*(K*logK))，其中N为strs的长度，K为strs中字符串的最大长度。遍历每个字符串时的复杂度为O(N)。使用内置排序函数对字符串中的字母进行排序的时间复杂度为O(K*logK)。空间复杂度：O(N*K)，map中存储的数据所占用的空间。统计词频解题：这种解题方法可以进一步优化，可以省去排序字符串的操作。仔细想想，一个单词最多由26个英文字母组成，难道你不能也做一个hashmap吗？例如：对于单词“aeat”：创建一个哈希映射{'a':2;'e'：1；t:1}key是出现的词，value是出现的频率。如果遍历每个key判断字母是否相等，再判断出现次数是否相等，这样显然比较复杂。每个字母的出现频率可以组成连续字符：每个字母a-z的出现频率：[2,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0]组成一个字符串："20001000000000000001000000"只需要判断每个单词的字母频率串是否相同即可。词频也可以优化，字母个数固定为26，直接建立一个长度为26的数组，其索引代表26个字母位，遍历单词中的字母。每出现一个字母，数组中的元素就代表字母值加1。这样就避免了排序操作Sortingletters问题解决：Java:classSolution{publicList>groupAnagrams(String[]strs){if(strs.length==0)returnnewArrayList<>();Map>map=newHashMap<>();//创建映射关系for(Strings:strs){//遍历字符串数组char[]chs=s.toCharArray();//转换为字符Arrays.sort(chs);//对字符串字母进行排序Stringkey=String.valueOf(chs);//转换为字符串if(!map.containsKey(key))map.put(key,newArrayList<>());//如果key不存在，则新建一个映射关系map.get(key).add(s);//添加对应Value所在的数组}returnnewArrayList(map.values());//返回一个Values数组}}Python:classSolution:defgroupAnagrams(self,strs:List[str])->List[List[str]]:ans=collections.defaultdict(list)#建立映射关系sinstrs:#遍历字符串数组ans[tuple(sorted(s))].append(s)#sorted(s):对字符串字母进行排序，并添加对应的Value数组returnans.values()#返回Values数组统计词频，求解问题:Java:classSolution{publicList>groupAnagrams(String[]strs){if(strs.length==0)returnnewArrayList<>();Map>map=newHashMap<>();//建立映射关系for(Strings:strs){//遍历字符串数组int[]count=newint[26];//Establisha26-lettermappingfor(charc:s.toCharArray())count[c-'a']++;//遍历词串的每个字母，统计每个字母出现的频率Stringkey=Arrays.toString(count);//转换为字符Stringif(!map.containsKey(key))map.put(key,newArrayList<>());//如果key不存在，则新建一个映射关系map.get(key).add(s);//添加对应Value所在的数组}returnnewArrayList(map.values());//返回Values组成的数组}}Python:class解决方法：defgroupAnagrams(self,strs:List[str])->List[List[str]]:ans=collections.defaultdict(list)#为s在strs中建立映射关系：#遍历字符串数组count=[0]*26#为c在s中建立一个26个字母的映射关系：#遍历单词串每个字母count[ord(c)-97]+=1#每个字母出现的频率（元素值）加1ans[tuple(count)].append(s)#添加到对应Value所在的数组中returnans.values()#返回一个由Values组成的数组欢迎关注微信公众号：爱写Bug