526互联

LeetCode 438. Find All Anagrams in a String 滑动窗口

发布时间 2023-07-23 22:37:19作者: Blackzxy

Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Solution

点击查看代码 
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        ans = []
        need = {}
        window = {}

        for ele in p:
            if ele not in need:
                need[ele]=1
            else:
                need[ele]+=1
        
        left = 0
        right = 0
        valid = 0

        while right<len(s):
            c = s[right]
            right +=1

            if c in need:
                if c in window:
                    window[c]+=1
                else: 
                    window[c]=1
                if window[c]==need[c]:
                    valid+=1
            
            while right-left>=len(p):
                if valid==len(need):
                    ans.append(left)
                d = s[left]
                left+=1
                if d in need:
                    if window[d]==need[d]:
                        valid-=1
                    window[d]-=1
        return ans