开始刷刷 leetcode. 让脑子不至于生锈。
今天做的是一个hard的题。题不很难，就是这个思路整个下来很有意思。
https://leetcode.com/problems/count-prefix-and-suffix-pairs-ii/description/ 简单来说就是给定一个words 字符串数组 ，然后，找到 (words[i] ,words[j]) 字符串对。 其中i < j 并且 words[i] 同时是words[j]的 前缀和后缀. 找到所有的符合要求的字符串对 。返回个数即可。
Example 1:
Input: words = [“a”,“aba”,“ababa”,“aa”] Output: 4 Explanation: In this example, the counted index pairs are: i = 0 and j = 1 because isPrefixAndSuffix(“a”, “aba”) is true. i = 0 and j = 2 because isPrefixAndSuffix(“a”, “ababa”) is true. i = 0 and j = 3 because isPrefixAndSuffix(“a”, “aa”) is true. i = 1 and j = 2 because isPrefixAndSuffix(“aba”, “ababa”) is true. Therefore, the answer is 4.
一开始一眼感觉简单的， 就是一个双层暴力遍历 找到符合要求的字符串对 计数即可。如下。
func countPrefixSuffixPairs(words []string) (ret int64) {
for i , v := range words {
for j := i +1 ; j < len(words); j ++ {
if isPrefixAndSuffix(v, words[j]) {
ret ++
}
}
}
return ret
}
func isPrefixAndSuffix(str1, str2 string) bool {
return len(str1)<= len(str2) && str2[:len(str1)] == str1 && str2[len(str2)-len(str1):] == str1
}
很显然 如果这个题不是hard 的话， 就ace了。 Time limit Exceeded.
看了下Test case 挂在了
//一个巨长的字符串数组，其中全是相同的元素。
testdata := []string{"aaaaa","aaaaa","aaaaa","aaaaa",...}
没法感觉路子是对的， 既然超时了。并且case 是相同元素 ，老方法就剪枝吧。
func countPrefixSuffixPairs1(words []string) (ret int64) {
mergeWords := []string{}
mergeCount := []int64{}
preWord := ""
mergeIndex := -1
for _, word := range words {
if preWord != word {
mergeWords = append(mergeWords, word)
mergeCount = append(mergeCount, 1)
mergeIndex++
preWord = word
} else {
mergeCount[mergeIndex]++
}
}
for i, v := range mergeWords {
var timesCount int64
for j := i + 1; j < len(mergeWords); j++ {
if isPrefixAndSuffix(v, mergeWords[j]) {
ret += mergeCount[j]
timesCount += mergeCount[j]
}
}
if mergeCount[i] > 1 {
for p := mergeCount[i] - 1; p > 0; p-- {
ret += p + timesCount
}
}
}
return ret
}
func countPrefixSuffixPairs(words []string) (ret int64) {
countListMap := map[string][]int{}
for i, word := range words {
var count int64
if c, exsist := countListMap[word]; exsist {
var z int
for z = 0; z < len(c) && c[z] <= i; z++ {
}
ret += int64(len(c) - z)
continue
}
tempList := []int{}
for j := i + 1; j < len(words); j++ {
if isPrefixAndSuffix(word, words[j]) {
//fmt.Println("prefix===>", word, words[j])
tempList = append(tempList, j)
count++
}
}
countListMap[word] = tempList
ret += count
}
return
}
用了两版 优化方案， 第一个 countPrefixSuffixPairs1
思路是既然是相同元素多， 先一个循环 将原本的字符串数据数组变成 俩个 一个是merge连续重复的之后，一个是对应的merge 个数。 然后再遍历merge 后的不重复的字符串数组。再统计次数，得出结果。
不过这种情况只能优化 前面遇到的那种case ，如果是非连续的重复数据。
testData := []string{"a","aa","aaa","aaa","a","aa","aaa","aaa"....}
这种数据，merge 结果就不行。
于是又针对这种case 去优化代码。有了countPrefixSuffixPairs
既然有大量非重复的字符串，我们可以用map[string][]int 记录该字符串的所有能组成前后缀的字符串index下标,放到同一个字符串list 中，存入map中 例如 {"word" => [1,3,5] } 。
这样 下一个遍历到同一字符串word的时候，可以拿到前一个同样字符串能用的下标列表。全部符合要求的下标[1,3,5]。 减去小于 当前word index， 剩下的就是符合要求的数量了。
跑一下， 很nice 过了上面的case ，但是倒在最后面了。。。。提示运行passed all testcase 但是时间还是超了。。。。
没法，只有想办法看是哪儿比较慢了， 其实到这儿我感觉思路已经优化差不多了，没有base case 方便对照。就只好用 pprof看 函数的火焰图。
很明显80%都是GC和内存分配 因为我们代码里面的 一个 map[string][]int{}. 遍历append 符合要求的index 到 []int. 比较费。
继续优化。 既然是append费时间。
func countPrefixSuffixPairs(words []string) (ret int64) {
countListMap := map[string]int64{}
countDupMap := map[string]map[string]interface{}{}
for i, word := range words {
var count int64
if dupMap, exsist := countDupMap[word]; exsist {
for k, _ := range dupMap {
countListMap[k] -= 1
}
}
if c, exsist := countListMap[word]; exsist {
ret += c
continue
}
for j := i + 1; j < len(words); j++ {
if isPrefixAndSuffix(word, words[j]) {
if x, exs := countDupMap[words[j]]; exs {
x[word] = nil
} else {
countDupMap[words[j]] = map[string]interface{}{
word: nil,
}
}
count++
}
}
countListMap[word] = count
ret += count
}
return
}
思路就是 俩个 map, 其中map[string]int64 记录 每个word对应有符合要求的数量。
比如 ["a","b", "aa", "a"] 其中"a” 对应有 “aa”,“a” 所以就是2.
一个map[string]map[string]interface 记录的就是一个字符串有多少个满足前后缀要求的集合。
比如有(“a”,“abba”) ，（“ab”,“abba”） 两对，
所以这个map 就是对应 "{abba" => {"a"=>nil,"ab"=>nil}}
前面用slice来记录 符合要求的坐标从而来计数。 而改良版本这个用map 来记录次数， 每次遍历的时候，先检查当前这个字符串如果有多少个字符串与之成对 。然后遍历这些字符串的countlistMap, 依次减一 ，因为当前这个字符串执行了。
然后检查当前字符串是否在countlistMap 有过记录。有的话 就跳过后续For ，直接加个count， 然后continue， 如果上述俩个 map 都没有，就执行 Foreach查找后续符合要求的字符串。将满足要求的数据扔进对应的map中。 这个版本不错。跑完 cpu 和 mem 都击败75%。想着也没啥优化空间了。 还挺窃喜。
结果看了下必败100%的实现
func countPrefixSuffixPairs(words []string) int64 {
set := make(map[string]int64)
c := int64(0)
for _, word := range words {
for k, v := range set {
if len(k) > len(word) {
continue
}
if word[:len(k)] != k {
continue
}
if word[len(word)-len(k):] != k {
continue
}
c += v
}
set[word]++
}
return c
}
ONZ… 只能说这大脑回路。 你还在苦巴巴沿着正向去优化。剪枝，用空间换时间，从slice 改成map。
你老老实实从 头 到尾遍历 所有符合要求的然后相加。 别人一个逆向思维，直接是每次遍历的当前字符串 和出现过的字符串set进行 比较，如果符合要求就直接 加上出现的个数就好了， Elegant！太美了。
至此结束，收获满满，很重要的一个启示。 就是一开始的思路很重要，或者是要灵活的去看问题。一个问题解决方案很多种，但是如果是走了一条很艰难的路，甚至是死路，还一个劲儿往上怼， 真的得不偿失了，浪费时间精力。还是要一开始想清楚，别急。