Clear Python sliding-window solution. O(n) time O(1) space


  • 0
    S
    class Solution(object):
        def findAnagrams(self, s, p):
            target = collections.Counter(p)
            rtList = []
            check = {}
    
            for i in range(len(s)):
                check[s[i]] = check.get(s[i], 0) + 1
                if i > len(p)-1:
                    check[s[i-len(p)]] -= 1
                    if check[s[i-len(p)]] == 0:
                        del check[s[i-len(p)]]
                if check == target:
                    rtList.append(i-len(p)+1)
            return rtList
    

    Use 1 dictionary to count elements in string S and substring P.
    While iterating through string S, update its dictionary and delete keys that have value 0. Then finally compares the 2 dictionaries.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.