零基础刷力扣Hot100|Day02 字母异位词

零基础刷力扣Hot100|Day02 字母异位词题目描述示例解题思路解法一排序法代码详细讲解解法二计数法代码详细讲解题目描述给你一个字符串数组请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。示例示例 1:输入: strs [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]解释在 strs 中没有字符串可以通过重新排列来形成 “bat”。字符串 “nat” 和 “tan” 是字母异位词因为它们可以重新排列以形成彼此。字符串 “ate” “eat” 和 “tea” 是字母异位词因为它们可以重新排列以形成彼此。示例 2:输入: strs [“”]输出: [[“”]]示例 3:输入: strs [“a”]输出: [[“a”]]提示1 strs.length 1040 strs[i].length 100strs[i] 仅包含小写字母解题思路字母异位词指的是由相同字母组成但排列顺序不同的字符串。要将它们分组关键在于为每一组字母异位词找到一个共同的标识。也就是说这道题的核心在于要找到一种方式将互为“字母异位词”的字符串映射到同一个键上。依着这个思路我们能够想到两种方式(1)排序法将每个字符串按照字典序排序这样排序后相同的字符串就为字母异位词。(2)计数法统计每个字符串中每个字母出现的次数有着相同计数的字符串互为字母异位词。解法一排序法这里我们可以使用哈希表以排序后的字符串作为键以原字符串组成的列表作为值遍历所有字符串并填入哈希表。最后将哈希表中的所有值收集到一个向量中返回。classSolution{public:vectorvectorstringgroupAnagrams(vectorstringstrs){// 哈希表键为排序后的字符串值为同一组字母异位词unordered_mapstring,vectorstringmp;for(strings:strs){string keys;// 复制原字符串sort(key.begin(),key.end());// 排序后作为键mp[key].push_back(s);// 将原字符串加入对应组}// 将哈希表中的所有组收集到结果向量中vectorvectorstringresult;for(autop:mp){result.push_back(p.second);}returnresult;}};代码详细讲解unordered_mapstring,vectorstringmp;首先创建一个哈希表mp键类型是string排序后的字符串值类型是vectorstring存储原字符串的列表。for(strings:strs){string keys;sort(key.begin(),key.end());mp[key].push_back(s);}对于strs中的每个字符串s进行如下操作将字符串s赋值给key然后对key中的字符依照字典序进行排序。排序后互为字母异位词的字符串会变成相同的字符串例如 “eat”、“tea” 排序后都变成 “aet”。以排序后的key为键在哈希表mp中查找对应的值。如果该键不存在mp[key] 会自动创建一个空的 vector。然后将原字符串 s 添加到这个向量末尾。这样所有具有相同key的字符串就被归到了一个vector中。vectorvectorstringresult;for(autop:mp){result.push_back(p.second);}遍历哈希表 mpp是一个键值对其中 p.first 是键排序后的字符串p.second是对应的值该组的所有原字符串。将每个 p.second即每组字符串的向量添加到结果向量 result 中。最后返回result即可。解法二计数法字母异位词由相同的字母组成因此每个字符串的字母出现次数频数统计是完全相同的。我们可以用一个长度为 26 的数组来记录每个字母出现的次数用这个数组作为键将原字符串分组存入哈希表。classSolution{public:vectorvectorstringgroupAnagrams(vectorstringstrs){// 使用 map键为长度为 26 的计数数组vectorint值为该组字符串列表mapvectorint,vectorstringmp;for(strings:strs){// 统计当前字符串中每个字母的出现次数vectorintcount(26,0);for(charc:s){count[c-a];}// 以计数数组为键将原字符串加入对应组mp[count].push_back(s);}vectorvectorstringresult;for(autop:mp){result.push_back(p.second);}returnresult;}};代码详细讲解mapvectorint,vectorstringmp;使用map容器定义哈希表键类型是vectorint长度为 26 的整型数组值类型是vectorstring存放原字符串的列表。for(strings:strs){vectorintcount(26,0);for(charc:s){count[c-a];}mp[count].push_back(s);}创建一个长度为 26 的 vectorint初始化为全 0用于统计 26 个小写字母的出现次数。遍历字符串的每个字符 c计算其相对于 ‘a’ 的偏移量c - ‘a’得到对应的索引0~25然后将该位置的值加 1。例如字符串 “eat”e→4‘e’-‘a’4、a→0、t→19统计后 count 为 [1,0,0,…,1,0,0,1,…]只有索引 0、4、19 处为 1-以count 作为键在 map 中查找对应的值。如果该键不存在mp[count] 会自动创建一个空的 vectorstring。然后将当前原字符串 s添加到这个向量的末尾。这样所有具有相同 count 的字符串就会被归入同一组。后续收集结果返回result部分计数法与排序法相同故不再赘述。