题目链接

剑指 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<=1041 <= strs.length <= 10^41<=strs.length<=104
• 0<=strs[i].length<=1000 <= strs[i].length <= 1000<=strs[i].length<=100
• strs[i]仅包含小写字母

解法：哈希表 + 排序

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

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

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

时间复杂度： O(n∗m∗logm)O(n * m * logm)O(n∗m∗logm)

C++代码：

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