题目

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例:

  1. 输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
  2. 输出:
  3. [
  4.   ["ate","eat","tea"],
  5.   ["nat","tan"],
  6.   ["bat"]
  7. ]

说明：

  • 所有输入均为小写字母。

  • 不考虑答案输出的顺序。

    方案一（提取模式）

    ```go func groupAnagrams(strs []string) [][]string { m := map[string][]string{}

    for _, str := range strs {

      sorted_str := getSortedString(str)
  if _, ok := m[sorted_str]; !ok {
      m[sorted_str] = []string{}
  }
  m[sorted_str] = append(m[sorted_str], str)

    }

    ret := [][]string{} for _, v := range m {

      ret = append(ret, v)

    } return ret }

func getSortedString(str string) string { sort_slice := sort.StringSlice(strings.Split(str, “”)) sort_slice.Sort() return strings.Join(sort_slice, “”) }


<a name="d3a3f2e4"></a>
# 方案二（积）
```go
func groupAnagrams(strs []string) [][]string {
    cnt := 0                        // 有几个字母异位词
    hash := map[int]int{}           // 记录每种异位词对应的下标数组
    prime := []int{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103}   // 用26个质数代表26个字母
    ans := [][]string{}
    for _,s := range strs {
        t := 1  
        for _,x := range s {        // 计算异位词对应的值
            t *= prime[x-'a']
        }
        if _,ok := hash[t]; !ok {   // 这类异位词没出现过，记录新下标
            hash[t] = cnt
            cnt++
            ans = append(ans, []string{})       // 初始化新下标的数组
        }
        ans[hash[t]] = append(ans[hash[t]], s)  // 将当前字符串加入该类异位词数组中
    }
    return ans
}
  • 很神奇的方案，之前想到过用加法的值来作为key，但是不能保证非字母异位词的和与字母异位词一定不同；
  • 此处用 prime 保证乘积一定不同

方案三

key 选择为 [26]int{} 每个位置为字符出现的次数

eg.

aabccc -> [26]int{2, 1, 3, 0, 0, ...}

方案四（排序）

原文

https://leetcode-cn.com/explore/learn/card/hash-table/206/practical-application-design-the-key/820/

官方题解

https://leetcode-cn.com/problems/group-anagrams/solution/zi-mu-yi-wei-ci-fen-zu-by-leetcode/