438. 找到字符串中所有字母异位词 难

438. 找到字符串中所有字母异位词

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
说明：

• 字母异位词指字母相同，但排列不同的字符串。
• 不考虑答案输出的顺序。

输入:**
s: “cbaebabacd” p: “abc”

输出:
[0, 6]

解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的字母异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的字母异位词。

解题思路

最开始想到，先分割每一个子串，然后每个子串依次比较。结果超时了。
于是，是否能够优化呢？比如动态规划。but，中间涉及到子串的变动，也不知道变动的关联关系，每次移动指针进去的是啥，出来的是啥不知道。
然后，注意到题目说只包含 小写字母 ==> 突然感觉被暗示了啥！
只需要枚举26个字母的个数，就能够判别子串是不是相等了。
于是，并有了2个26位数组比较。

//滑动窗口 + 哈希键计数
func findAnagrams(s string, p string) []int {
    if len(s) == 0 || len(p) == 0|| len(s) < len(p) {
        return []int{}
    }
    countmap := make([]int, 26)                        //p, 定义目标字符存储hasMap
    tmpmap := make([]int, 26)                        //s, 定义检索需要的hasMap 
    for i := 0; i < len(p); i++ {            //1，移动滑动窗口
        countmap[p[i]-'a'] += 1
        tmpmap[s[i]-'a'] += 1
    }
    var ret []int
    for i := 0; i < len(s)-len(p)+1; i++ {    //2，在窗口内，比较窗口的值
        if isEqual(countmap, tmpmap) {
            ret = append(ret, i)
        }
        tmpmap[s[i]-'a'] -= 1                //3，记录哈希键 计数
        idx := i + len(p)
        if idx < len(s){
            tmpmap[s[idx]-'a'] += 1
        }
    }
    return ret
}
func isEqual(a, b []int)bool {                //4，比较函数，滑动窗口比较
    for i := 0; i < 26; i++ {
        if a[i] != b[i] {
            return false
        }
    }
    return true
}

// 子串排序，再比较。貌似超时。
func findAnagrams(s string, p string) []int {
    if len(s) == 0 || len(p) == 0|| len(s) < len(p) {
        return []int{}
    }
    tmpp := []byte(p)
    sort.Slice(tmpp, func(i,j int)bool{
        return tmpp[i] < tmpp[j]
    })
    var ret []int
    for i := 0; i < len(s)-len(p)+1; i++ {
        tmp := []byte(s[i:i+len(p)])
        sort.Slice(tmp, func(i,j int)bool{
            return tmp[i] < tmp[j]
        })
        if string(tmpp) == string(tmp) {
            ret = append(ret, i)
        }
    }
    return ret
}