Python sliding window


  • 0
    Y
    def check_inclusion(s, t):
        # https://leetcode.com/problems/permutation-in-string/description/
        #
        # O(s) space and O(t + s) time; this is a sliding window algorithm
        if len(s) > len(t):
            return False
        chars = set(s)
        rem = collections.Counter(s)
        m, n = len(s), len(t)
        # initialize the window
        for j in xrange(m):
            if t[j] in chars:
                rem[t[j]] -= 1
                if not rem[t[j]]:
                    del rem[t[j]]
        for j in xrange(n - m):
            if not rem:
                return True
            if t[j] in chars:
                # char in s is out of the window
                rem[t[j]] += 1
                if not rem[t[j]]:
                    del rem[t[j]]
            if t[j + m] in chars:
                # char in s is in the window
                rem[t[j + m]] -= 1
                if not rem[t[j + m]]:
                    del rem[t[j + m]]
        return not rem
    

Log in to reply
 

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