Python Sliding Window dict solution


  • 0
    J
    Sliding window. O(n). BTW, should this really be a easy question?
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        if len(s) < len(p):
            return []
        dic = {}
        for c in p:
            dic[c] = dic.get(c,0) + 1
        res = []
        start_idx = 0
        local = {}
        for idx,c in enumerate(s):
            if idx < len(p):
                local[c] = local.get(c,0) + 1
            else:
                if local == dic:
                    res.append(start_idx)
                #updates dic
                local[s[start_idx]] -= 1
                if local[s[start_idx]] == 0:
                    del local[s[start_idx]]
                local[c] = local.get(c,0) + 1
                start_idx += 1
        #deal with last one
        if local == dic:
            res.append(start_idx)
        return res

Log in to reply
 

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