网站建设有什么专业术语,广州网络推广公司有哪些,oppo手机网站建设需求分析,广州市品牌网站建设怎么样题目链接 剑指 Offer II 033. 变位词组 mid 题目描述
给定一个字符串数组 strs#xff0c;将 变位词 组合在一起。 可以按任意顺序返回结果列表。
注意#xff1a;若两个字符串中每个字符出现的次数都相同#xff0c;则称它们互为变位词。
示例 1: 输入: strs [“eat”,…题目链接 剑指 Offer II 033. 变位词组 mid 题目描述
给定一个字符串数组 strs将 变位词 组合在一起。 可以按任意顺序返回结果列表。
注意若两个字符串中每个字符出现的次数都相同则称它们互为变位词。
示例 1: 输入: strs [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”] 输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]] 示例 2: 输入: strs [“”] 输出: [[“”]] 示例 3: 输入: strs [“a”] 输出: [[“a”]] 提示
1strs.length1041 strs.length 10^41strs.length1040strs[i].length1000 strs[i].length 1000strs[i].length100strs[i]仅包含小写字母
解法哈希表 排序
将 变位词 排序之后所有的变位词都相同了。
我们可以将排序后的 变位词 当作哈希表的 key原字符串当作 val插入到每一个 key对应的列表中。
最后遍历一遍将哈希表中的列表取出来加到答案列表中即可。
时间复杂度 O(n∗m∗logm)O(n * m * logm)O(n∗m∗logm)
C代码
class Solution {
public:vectorvectorstring groupAnagrams(vectorstring strs) {unordered_mapstring,vectorstring m;for(auto s:strs){string ss s;sort(s.begin(),s.end());m[s].push_back(ss);}vectorvectorstring ans(m.size());int idx 0;for(auto [_,v]:m){ans[idx] v;}return ans;}
};
Python代码
class Solution:def groupAnagrams(self, strs: List[str]) - List[List[str]]:m collections.defaultdict(list)for s in strs:key .join(sorted(s))m[key].append(s)return list(m.values())
