剑指 Offer II 033. 变位词组

力扣

给定一个字符串数组 strs ，将 变位词 组合在一起。 可以按任意顺序返回结果列表。

注意：若两个字符串中每个字符出现的次数都相同，则称它们互为变位词。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2:

输入: strs = [""]
输出: [[""]]
示例 3:

输入: strs = ["a"]
输出: [["a"]]
 

提示：

1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母

通过位哈希的方法映射词语，并把哈希后的数组作为map的键，词数组作为值

class Solution:
    def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
        def anagrams(s: str) -> list[int]:
            dict = [0 for _ in range(26)]
            for i in s:
                dict[ord(i) - ord('a')] += 1
            return dict
        strMap = {}
        ans = []
        for s in strs:
            dict = anagrams(s)
            hashCode = hash(tuple(dict)) #转成tuple才能哈希
            res = strMap.get(hashCode,[])
            res.append(s)
            strMap[hashCode] = res

        for words in strMap.values():
            ans.append(words)
        return ans

func anagramDict(s string) (dict [26]int) {
	n := len(s)
	for i := 0; i < n; i++ {
		index := s[i] - 'a'
		dict[index]++
	}
	return
}

func groupAnagrams(strs []string) [][]string {
	strMap := make(map[[26]int][]string)
	for _, s := range strs {
		dict := anagramDict(s)
		if value, ok := strMap[dict]; ok {
			strMap[dict] = append(value, s)
		} else {
			strMap[dict] = []string{s}
		}
	}
	var ans [][]string
	for _, value := range strMap {
		ans = append(ans, value)
	}
	return ans
}