leetcode学习笔记(字符串中的所有变位词)

leetcode学习笔记(字符串中的所有变位词) 438.字符串中的所有变位词

我觉得可以，但是超时了

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        s = list(s)
        p = list(p)
        l = len(p)
        res = []

        for i in range(len(s)):
            m = 0
            k = s[i:i+l]
            for j in range(l):
                if p[j] in k :
                    k.remove(p[j])
                else:
                    m += 1
            if m == 0:    
                res.append(i)

        return res

官方答案(滑动窗口)

 class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        slen, plen = len(s), len(p)
        need = Counter(p)
        window = Counter()
        left, right, valid = 0, 0, 0
        res = []
        while right < slen:
            c = s[right]
            right += 1

            if need.get(c):
                window[c] += 1
                if window[c] == need[c]:
                    valid += 1

            while right - left >= plen:
                if valid == len(need):
                    res.append(left)
                
                d = s[left]
                left += 1

                if need.get(d):
                    if window[d] == need[d]:
                        valid -= 1
                    window[d] -= 1
        return res