Simple Python solution by maintaining hash of running window.

  • 1

    This code is inspired by some of the solutions already discussed here. But I hope it is easier to understand as compared to other solutions.

    class Solution(object):

    def findAnagrams(self, s, p):
        :type s: str
        :type p: str
        :rtype: List[int]
        indices =[]
        p_hash = [0]*26
        s_hash = [0]*26
        p_len = len(p)
        s_len = len(s)
        if p_len > s_len:
            return indices 
        # build character hash for p
        for char in p:
            p_hash[ord(char)- ord('a')] += 1
        Iterate over s
        Implicitly maintain a hash for each substring of len(p) in s by a running window approach
        So we update the hash by adding the new character of the window and removing the oldest character of the window
        Maintaining the running hash of substring.
        When the index of s is >= len(p):
            push each char in p_hash
            if p_hash == s_hash: 
                a hit
            remove the oldest char of window i.e. (idx - p_len)+1 
        for idx, char in enumerate(s):
            s_hash[ord(char) - ord('a')] +=1
            if idx+1 >= p_len:
                if s_hash == p_hash:
                    indices.append(idx - p_len +1)
                s_hash[ord(s[idx - p_len +1]) - ord('a')] -=1
        return indices

Log in to reply

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