剑指 Offer II 015. 字符串中的所有变位词

剑指 Offer II 015. 字符串中的所有变位词

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        s_len,p_len=len(s),len(p)
        if s_len<p_len:
            return []
        ans=[]
        count=[0]*26
        for i in range(p_len):
            count[ord(p[i])-ord('a')]-=1
            count[ord(s[i])-ord('a')]+=1
        differ=0
        for c in count:
            if c!=0:
                differ+=1
        if differ==0:
            ans.append(0)
        for i in range(s_len-p_len):
            left=ord(s[i])-ord('a')         #滑动窗口左边丢弃的字母
            right=ord(s[i+p_len])-ord('a')  #滑动窗口右边加入的字母
            if count[left]==1:     #本来字母left的数量多一个，丢弃后differ--
                differ-=1
            elif count[left]==0:
                differ+=1
            count[left]-=1

            if count[right]==0:
                differ+=1
            elif count[right]==-1:
                differ-=1
            count[right]+=1
            
            if differ==0:
                ans.append(i+1)      
        return ans