算法导学之眼前一亮（持续更新）

novice-dxx 2019-10-25 原文

算法导学之眼前一亮（持续更新）

本篇文章仅记录在平时刷题过程中，让人眼前一亮的处理思路，所以本篇文章适合算法爱好者阅读及参考，没有算法功底的程序猿们，建议不用花费太多的时间在本篇文章

1，题目描述：给定一个字符串数组，请根据“相同字符集”进行分组（摘自 LintCode 49）

例：Input: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],

Output:[

[“ate”,”eat”,”tea”],
[“nat”,”tan”],
[“bat”]
]

基础分析：这类问题的常见处理并不难，只需要将每个字符记录对应值，内部循环比较，外部循环子串数组即可，时间复杂度 O(K²[子串平均长度] * N * Log(N)²)

晋级分析：我在基础之上，将字符串的和存了下来，将内部循环比较的次数降低，时间复杂度可以达到 O(K² * N * Log(N) * Min(N)[代表字符串和相同的次数])

高级分析：首先引进一组概念：正整数唯一分解定理，每个大于1的自然数，要么本身为质数，要么可以由2个或以上的质数相乘，且组合唯一；

上述定理结合问题来看，我们仅需要将字符串中的每个字符与质数一一对应，并将字符串所有字符对应的质数乘积保存下来，即可确保字符串的 hash 唯一，时间复杂度 O(K * N * Log(N))

Coding ：

 1 func GroupAnagramsOpt(strs []string) [][]string {
 2     var res [][]string
 3     strMap := make(map[int][]string)
 4     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}
 5 
 6     for _, str := range strs {
 7         sum := 1
 8         for _, char := range str {
 9             sum = prime[char-'a'] * sum
10         }
11         if _, ok := strMap[sum]; !ok {
12             strMap[sum] = []string{str}
13         } else {
14             strMap[sum] = append(strMap[sum], str)
15         }
16     }
17 
18     for _, v := range strMap {
19         res = append(res, v)
20     }
21 
22     return res
23 }