class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
}
};
面试题 10.02. 变位词组
编写一种方法，对字符串数组进行排序，将所有变位词组合在一起。变位词是指字母相同，但排列不同的字符串。
注意：本题相对原题稍作修改
示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
说明：
原站题解
golang 解法, 执行用时: 16 ms, 内存消耗: 7.6 MB, 提交时间: 2022-11-14 11:20:03
func groupAnagrams(strs []string) [][]string {
mp := map[string][]string{}
for _, str := range strs {
s := []byte(str)
sort.Slice(s, func(i, j int) bool { return s[i] < s[j] })
sortedStr := string(s)
mp[sortedStr] = append(mp[sortedStr], str)
}
ans := make([][]string, 0, len(mp))
for _, v := range mp {
ans = append(ans, v)
}
return ans
}
golang 解法, 执行用时: 12 ms, 内存消耗: 8.2 MB, 提交时间: 2022-11-14 11:19:16
func groupAnagrams(strs []string) [][]string {
mp := map[[26]int][]string{}
for _, str := range strs {
cnt := [26]int{}
for _, b := range str {
cnt[b-'a']++
}
mp[cnt] = append(mp[cnt], str)
}
ans := make([][]string, 0, len(mp))
for _, v := range mp {
ans = append(ans, v)
}
return ans
}
python3 解法, 执行用时: 72 ms, 内存消耗: 19.7 MB, 提交时间: 2022-11-14 11:18:49
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
mp = collections.defaultdict(list)
for st in strs:
counts = [0] * 26
for ch in st:
counts[ord(ch) - ord("a")] += 1
# 需要将 list 转换成 tuple 才能进行哈希
mp[tuple(counts)].append(st)
return list(mp.values())
python3 解法, 执行用时: 64 ms, 内存消耗: 17.9 MB, 提交时间: 2022-11-14 11:18:27
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
mp = collections.defaultdict(list)
for st in strs:
key = "".join(sorted(st))
mp[key].append(st)
return list(mp.values())