Python solution using sliding window and list


  • 0
    class Solution(object):
        def findAnagrams(self, s, p):
            len_s = len(s)
            len_p = len(p)
            if len_s < len_p:
                return []
            flag = [0] * 26
            for c in p:
                flag[ord(c)-ord('a')] += 1
            output = []
            window = [0] * 26
            
            for idx, c in enumerate(s):
                if idx < len_p:
                    window[ord(c)-ord('a')]+=1
                    continue
                if window == flag:
                    output.append(idx-len_p)
                window[ord(c)-ord('a')]+=1
                window[ord(s[idx-len_p])-ord('a')]-=1
            if window == flag: ## be careful of the end
                    output.append(idx-len_p+1)
            return output
    

    With sliding window, you don't need to reconstruct substrings of s to compare with p in each step; You only need to take care of the head and tail each time. So when p is very long, you do not have the TLE issue.


Log in to reply
 

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