Python Sliding Window Solution using Counter


  • 0
    S

    @WKVictor nice solution, I tried a similar idea in python but python's heap does not have remove function.


  • 0
    H

    @fatenaught yes, otherwise, a key with value 0 will be left. This key should be deleted to ensure the cs can equal with cp.


  • 0
    C

    @weijuemin Notice the beginning of his code, from collections import Counter.


  • 0

    @fatenaught
    It is necessary, otherwise Counter({'a': 0, 'b': 1}) will not equal to Counter({'b': 1})


  • 1

    Similar idea, but somewhat compact (obscure) code.

    The main difference is that we counter letters in p as positive, letters in s as negative.
    So instead of deleting 0 counts, we can simply check all values in the sliding Counter

    def findAnagrams(self, s, p):
        cnt, lp, s = Counter(p), len(p), s+'|'                                    
        cnt.subtract(s[-1] + s[:lp-1])                                            # append '|' to s, make s[-1] valid when s=''
        return [i for i in xrange(len(s)-lp+1) if cnt.update({s[i-1+lp]: -1}) or  # delete front letter by 1 when sliding forward
                                                  cnt.update({s[i-1   ]:  1}) or  # add the letter in the back to counter
                                                  not any(cnt.values())]          # check all letters count to 0
    
    

  • 0
    F

    @waigx gotcha, thx.


  • 0
    F

    @hw1472 thanks.


  • 1
    A

    @waigx Very smart solution using pos/neg counts and Counter.update(). I modified your code a little to make it more straightforward.

    class Solution2(object):
        def findAnagrams(self, s, p):
            """
            :type s: str
            :type p: str
            :rtype: List[int]
            """
            ns, np, res = len(s), len(p), []
            cnt = Counter(p)  # positive count for p
            cnt.subtract(s[:np-1])  # negative count for s
            for i in range(np-1, ns):
                cnt.update({s[i]: -1})  # decrease window right
                i < np or cnt.update({s[i-np]: 1})  # increase window left
                if not any(cnt.values()):  # check all letters count 0
                    res.append(i-(np-1))
            return res
    

  • 0
    L

    @algowl I don't think you need to check i < np in the for loop. The following should work.

    class Solution(object):
        def findAnagrams(self, s, p):
            """
            :type s: str
            :type p: str
            :rtype: List[int]
            """
            res = []
            cnt = Counter(p)
            cnt.subtract(s[:len(p) - 1])
            for i in range(len(p) - 1, len(s)):
                cnt.update({s[i]: -1})
                if not any(cnt.values()):
                    res.append(i - len(p) + 1)
                cnt.update({s[i - len(p) + 1]: 1})
            return res
    

  • 0
    F
    This post is deleted!

Log in to reply
 

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