Readable Python solution [235ms]


  • 0
    class Solution(object):
        def findAnagrams(self, s, p):
            """
            :type s: str
            :type p: str
            :rtype: List[int]
            """
            if len(s) < len(p):
                return []
            
            # Negative character count of pattern
            w = {}
            for c in p:
                w[c] = w.get(c, 0) - 1
                
            r = []
            d = len(p) - 1
            for i, c in enumerate(s):
                
                # Add next character to the moving window
                w[c] = w.get(c, 0) + 1
                
                # Incomplete window
                if i < d:
                    continue
                
                # All zeros indicate an anagram match
                for x in w.values():
                    if x:
                        break
                else:
                    r.append(i - d)
                    
                # Remove first character from the moving window
                w[s[i - d]] -= 1
    
            return r
    

Log in to reply
 

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