Python solution using modified sliding window algorithm, beating 96%


  • 0
    J

    Similar to the sliding window algorithm. But a copy of d, the map from the letters in p to their frequencies, is stored, so that we can directly skip those letters in s that do not appear in p.

    class Solution(object):
        def findAnagrams(self, s, p):
            """
            :type s: str
            :type p: str
            :rtype: List[int]
            """
            
            d = {}
            for c in p:
                d[c] = d.get(c, 0) + 1
            store = dict(d)
            
            lo, hi = 0, 0
            m, n = len(s), len(p)
            res = []
            
            while hi < m:
                if s[hi] in d and d[s[hi]] > 0:
                    d[s[hi]] -= 1
                    hi += 1
                    if hi - lo == n:
                        res += [lo]
                        d[s[lo]] += 1
                        lo += 1
                # If s[hi] does not appear in p, 'lo' can jump to 'hi + 1' directly
                elif s[hi] not in d:
                    lo = hi = hi + 1
                    d = dict(store)
                else:
                    d[s[lo]] += 1
                    lo += 1
                    
            return res
                   
    

Log in to reply
 

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