剑指 Offer II 033. 变位词组

题目链接

剑指 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”]]

提示：

• $1<=strs.length<=10^4$
• $0<=strs[i].length<=100$
• strs[i]仅包含小写字母

解法：哈希表 + 排序

将 变位词 排序之后，所有的变位词都相同了。

我们可以将排序后的 变位词 当作哈希表的 key，原字符串当作 val，插入到每一个 key对应的列表中。

最后遍历一遍，将哈希表中的列表取出来加到答案列表中即可。

时间复杂度： $O(n\ast m\ast logm)$

C++代码：

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string,vector<string>> m;for(auto &s:strs){string ss = s;sort(s.begin(),s.end());m[s].push_back(ss);}vector<vector<string>> 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())