LeetCode438-找到字符串中所有字母异位词

题目链接

滑动窗口，相比应该不用多说了，就是一个抽象的窗口，每次验证窗口内的值。

但是本题其实也可以不算滑动窗口，因为这个窗口是定长的，相当于每次的移动方式是已知的。

就变成了一个定长滑动字符串匹配问题。

先写个暴力，超时了

每次对窗口内的字符串排序，然后比较：

var q []byte
func findAnagrams(s string, p string) []int {
          
   
    
    ans:=make([]int,0)
    if len(s)<len(p){
          
   
        return ans
    }
    l,r:=0,len(p)-1
    tmp:=[]byte(s[:len(p)])
    ss:=strings.Split(p,"")
    sort.Strings(ss)
    p=strings.Join(ss,"")
    for r<len(s){
          
   
        if check(tmp,p){
          
   
            ans=append(ans,l)
        }
        r++
        l++
        if r<len(s){
          
   
            tmp=append(tmp,s[r])
        }
        
        tmp=tmp[1:]
    }
    return ans
}

func check(a []byte,o string)bool{
          
   
    //fmt.Println(string(a),o)
    q=make([]byte,len(a))
    copy(q,a)
    sort.Sort(sortRunes(q))    
    return string(q)==o
}

type sortRunes []byte

func (s sortRunes) Less(i, j int) bool {
          
   
    return s[i] < s[j]
}

func (s sortRunes) Swap(i, j int) {
          
   
    s[i], s[j] = s[j], s[i]
}

func (s sortRunes) Len() int {
          
   
    return len(s)
}

没啥悬念，超时了。怎么优化呢 其实按照以往思路，也可以写个统计数组，来记录每个字符出现的次数。

方法一：记录字符出现次数

官姐有写，算是比较常规的方法，不展开了。

方法二： 字符串哈希

哈希这个东西，就很神奇，可以把一个字符串映射成一个数，这样子滑动窗口验证的时候，就只需要比较两次。 但是普通哈希，不同顺序的值是不一样的呀，比如，"abc"的哈希值一定要和"cba"不一样，这样有和题目要求冲突了，怎么办呢？

我们可以自定义哈希函数，这里笔者用了双哈希，其实单哈希也可以，主要是自定义哈希函数比较重要。 我定义： hash函数 f 1 ( s ) = ( ∑ i 0 → l e n ( n o w S t r ) − 1 i n t 64 ( n o w S t r [ i ] ) 2 ) m o d   M o d 1 f1(s)=(displaystyle sum^{}_{i 0 o len(nowStr)-1}{int64(nowStr[i])^2})mod:Mod1 f1(s)=(i0→len(nowStr)−1∑int64(nowStr[i])2)modMod1 hash函数 f 2 ( s ) = ( ∑ i 0 → l e n ( n o w S t r ) − 1 i n t 64 ( n o w S t r [ i ] ) 3 ) m o d   M o d 2 f2(s)=(displaystyle sum^{}_{i 0 o len(nowStr)-1}{int64(nowStr[i])^3})mod:Mod2 f2(s)=(i0→len(nowStr)−1∑int64(nowStr[i])3)modMod2 其实就是各位数的平方和与各位数的立方和，Mod1与Mod2是两个大整数，用来减少哈希冲突的。

var q []byte
var mod1,mod2 int64
func findAnagrams(s string, p string) []int {
          
   
    mod1=1e15+7
    mod2=1e15+9
    ans:=make([]int,0)
    if len(s)<len(p){
          
   
        return ans
    }
    l,r:=0,len(p)-1
    now:=cal(s[:len(p)])
    pp:=cal(p)
    for r<len(s){
          
   
        if check(now,pp){
          
   
            ans=append(ans,l)
        }
        r++
        if r<len(s){
          
   
            now[0]+=int64(s[r])*int64(s[r])
            now[1]+=int64(s[r])*int64(s[r])*int64(s[r])
            now[0]%=mod1
            now[1]%=mod2
        }
        
        now[0]-=int64(s[l])*int64(s[l])
        now[1]-=int64(s[l])*int64(s[l])*int64(s[l])
        now[0]=(now[0]+mod1)%mod1
        now[1]=(now[1]+mod2)%mod2
        l++
    }
    return ans
}

func cal(s string)(ans []int64){
          
   
    a,b:=int64(0),int64(0)
    for i:=range s{
          
   
        a+=int64(s[i])*int64(s[i])
        b+=int64(s[i])*int64(s[i])*int64(s[i])
        a%=mod1
        b%=mod2
    }
    ans=append(ans,a,b)
    return
}

func check(a,b []int64)bool{
          
   
    return a[0]==b[0] && a[1]==b[1]
}

小小坑点

题目描述当中，没有规定len(s)≥len(p)，所以需要进行特判。