LeetCode 30 串联所有单词的子串

题目：

给定一个字符串 s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符 ，但不需要考虑 words 中单词串联的顺序。

解题：

逐个判断单词是否连续出现在字符串中

代码：

func findSubstring(s string, words []string) []int {
    var r []int
    lw := len(words[0])
    l := len(words) * lw
    ls := len(s)
    if ls < l {
        return r
    }
    for i := 0; i <= ls-l; i++ {
        tmp := make([]string, len(words))
        copy(tmp, words)
        for j := i; j < j+l; j += lw {
            str := s[j : j+lw]
            k := 0
            for ii, v := range tmp {
                if v == str {
                    tmp[ii] = tmp[len(tmp)-1]
                    k++
                    break
                }
            }
            if k == 0 {
                break
            }
            tmp = tmp[:len(tmp)-1]
            if len(tmp) == 0 {
                r = append(r, i)
                break
            }
        }
    }
    return r
}

官方解答： 

// 滑动窗口
func findSubstring(s string, words []string) (ans []int) {
    ls, m, n := len(s), len(words), len(words[0])
    for i := 0; i < n && i+m*n <= ls; i++ {
        differ := map[string]int{}
        for j := 0; j < m; j++ {
            differ[s[i+j*n:i+(j+1)*n]]++
        }
        for _, word := range words {
            differ[word]--
            if differ[word] == 0 {
                delete(differ, word)
            }
        }
        for start := i; start < ls-m*n+1; start += n {
            if start != i {
                word := s[start+(m-1)*n : start+m*n]
                differ[word]++
                if differ[word] == 0 {
                    delete(differ, word)
                }
                word = s[start-n : start]
                differ[word]--
                if differ[word] == 0 {
                    delete(differ, word)
                }
            }
            if len(differ) == 0 {
                ans = append(ans, start)
            }
        }
    }
    return
}

比官方效率整整差了20倍。。。