Python, Simple with Explanation


  • 7

    For each window representing a substring of s2 of length len(s1), we want to check if the count of the window is equal to the count of s1. Here, the count of a string is the list of: [the number of a's it has, the number of b's,... , the number of z's.]

    We can maintain the window by deleting the value of s2[i - len(s1)] when it gets larger than len(s1). After, we only need to check if it is equal to the target. Working with list values of [0, 1,..., 25] instead of 'a'-'z' makes it easier to count later.

    def checkInclusion(self, s1, s2):
        A = [ord(x) - ord('a') for x in s1]
        B = [ord(x) - ord('a') for x in s2]
        
        target = [0] * 26
        for x in A:
            target[x] += 1
        
        window = [0] * 26
        for i, x in enumerate(B):
            window[x] += 1
            if i >= len(A):
                window[B[i - len(A)]] -= 1
            if window == target:
                return True
        return False
    

  • 0

    The fourth line from bottom should be:

    window[B[i - len(A)]] -= 1
    

  • 0

    My rewrite:

    class Solution(object):
        def checkInclusion(self, s1, s2):
            from string import lowercase
            from copy import deepcopy
            s1_counter = collections.defaultdict(int, {i:0 for i in lowercase})
            s2_window_counter = deepcopy(s1_counter)
            s1_counter.update(collections.Counter(s1))
            s2_window_counter.update(collections.Counter(s2[:len(s1)]))
            if s1_counter == s2_window_counter: return True
            for i in range(len(s1), len(s2)):
                s2_window_counter[s2[i]] += 1
                s2_window_counter[s2[i - len(s1)]] -= 1
                if s1_counter == s2_window_counter:
                    return True
            return False
    

  • 0

    Like the cleverness of how you're dealing with maintaining the window, but this will be slower than just maintaining a dict of counts and just dealing with left and right end points. They will be asymptotically the same but the C (constant) factor here will be relatively big.


  • 0

    @Ellest I'm not sure what you mean, are you referring to a solution like this? Initially I had a dict of counts as you suggested, but I checked dict1 == dict2 and it TLE'd on the contest. We need to manage also the non-zeroness in constant time.

    def checkInclusion(self, s1, s2):
        A = [ord(x) - ord('a') for x in s1]
        B = [ord(x) - ord('a') for x in s2]
    
        count = [0] * 26
        for x in A:
            count[x] -= 1
        self.nonzero = sum(x != 0 for x in count)
        
        def update(char, delta):
            count[char] += delta
            if count[char] == 0:
                self.nonzero -= 1
            elif count[char] == delta:
                self.nonzero += 1
        
        for i, x in enumerate(B):
            update(x, 1)
            if i >= len(A):
                update(B[i - len(A)], -1)
    
            if self.nonzero == 0:
                return True
        return False
    

  • 0

    @awice
    You only need to keep track of a single dictionary of counts. Here's my solution:

        def checkInclusion(self, s1, s2):
            if not s1: return True
            letters = collections.Counter(s1)
            lCnt, j = len(s1), 0
            for i in range(len(s2)):
                if s2[i] not in letters or letters[s2[i]] == 0 : # DNE or depleted
                    while j < i and s2[j] != s2[i]: 
                        letters[s2[j]] += 1; j += 1
                    if s2[j] in letters: letters[s2[j]] += 1 # if in char map
                    j += 1 
                elif i-j+1 == lCnt: return True
                if s2[i] in letters: letters[s2[i]] -= 1
            return False
    

    Since we're putting back used characters when an invalid condition is met (non-existent char or char that has been depleted) we can assume that our count dict will at most contain counts we started with. Thus we just need to check if our current window size matches the length of s1 in order to validate the match.


  • 2

    Just use a Counter:

    def checkInclusion(self, s1, s2):
            from collections import Counter
            m, n = len(s1), len(s2)
            cur, target = Counter(s2[:m]), Counter(s1)
            if target == cur: return True
            for i in range(n-m):
                cur[s2[i]] -= 1
                cur[s2[i+m]] += 1
                cur += Counter()
                if cur == target: return True
            return False

  • 0

    @lee215
    Counters are basically dictionaries, are they not? Using a counter will have the same issue as using an array of size 26 as you'd be doing 26 comparisons each time in the worst case(in the case you have all letters of the alphabet present). I wanted to avoid doing just that with keeping my maintaining my window with an invariant. Yes, you can argue 26 is just a constant factor so it doesn't matter, but it just seemed unnecessary to me. Unless you're telling me that comparison between Counters are done by some how hashing the two object and comparing just the hash, iterating over the dict is unavoidable.


  • 0

    @lee215 Just a little variation idea for the loop:

            for enter, leave in zip(s2[m:], s2):
                cur[leave] -= 1
                cur[enter] += 1
    

  • 0

    @Ellest
    I didn't keep the key with value 0. The length of dictionary is not 26 in most of cases.


  • 0

    @lee215
    I said it's 26 in the worst case. Like I said I just thought there is a lot of unnecessary comparisons needed to be made when using a counter.


  • 0
    W

    good solution, here is a more compact version:

    def checkInclusion(self, s1, s2):
            l1 = [0]*26
            l2 = [0]*26
            for x in s1:
                l1[ord(x) - ord('a')] += 1
            
            for i in xrange(len(s2)):
                l2[ord(s2[i]) - ord('a')] += 1
                if i >= len(s1):
                    l2[ord(s2[i-len(s1)]) - ord('a')] -= 1
                if l1 == l2:
                    return True
            return False
    

  • 1
    S

    @lee215 said in Python, Simple with Explanation:

    cur += Counter()

    Hey Lee, can you tell what is "cur += Counter()" about? why is this needed?


  • 2

    @sha256pki
    It will remove all keys with value zero and negative.


Log in to reply
 

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