Desciption

Given two strings s and p, return an array of all the start indices of p\’s anagrams in s. You may return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Input: s = “cbaebabacd”, p = “abc”
Output: [0,6]
Explanation:
The substring with start index = 0 is “cba”, which is an anagram of “abc”.
The substring with start index = 6 is “bac”, which is an anagram of “abc”.

• https://leetcode.com/problems/find-all-anagrams-in-a-string/

Solution

sliding windows

Code

• submit code

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        # Creat a NeedDict5
        need_dict = {}
        for m in p:
            need_dict[m] = need_dict.get(m,0) + 1


        left = 0
        right = 0
        valid = 0

        window_dict = {}

        result = []

        tmp = ""

        while left < len(s):
            INPUT = s[left]
            left += 1

            tmp += INPUT

            window_dict[INPUT] = window_dict.get(INPUT,0) + 1

            if(need_dict.get(INPUT)):
                if(need_dict.get(INPUT) == window_dict.get(INPUT,0)):
                    valid += 1


            while valid == len(need_dict) and right < len(s):
                OUTPUT = s[right]
                right += 1

                if(len(tmp) == len(p)):
                    result.append(right - 1)

                tmp = tmp[1:]

                window_dict[OUTPUT] = window_dict.get(OUTPUT) - 1

                if(need_dict.get(OUTPUT,0) > window_dict.get(OUTPUT,0) and need_dict.get(OUTPUT) != 0):
                    valid -= 1


        return result        

• full code

class Solution:
    def findAnagrams(self, s: str, p: str):

        result = []

        need_dict = {}
        for i in p:
            need_dict[i] = need_dict.get(i,0) + 1


        right = 0
        left = 0
        valid = 0

        wind_dict = {}

        tmp = ""

        while left < len(s):
            In = s[left]
            left += 1
            tmp += In
            print("1_tmp:\t" + tmp)
            wind_dict[In] = wind_dict.get(In, 0) + 1

            if(need_dict.get(In)):
                if(need_dict.get(In) == wind_dict.get(In)):
                    valid += 1

            while valid == len(need_dict) and right < len(s):
                print("-------------before desec----------------")
                print("valid:\t" + str(valid))
                print("tmp\t" + tmp)
                print("###############################")
                OUT = s[right]
                right += 1

                if(len(tmp) == len(p)):
                    result.append(right - 1)

                tmp = tmp[1:]
                wind_dict[OUT] = wind_dict.get(OUT, 0) - 1

                if(need_dict.get(OUT,0) > wind_dict.get(OUT,0) and need_dict.get(OUT) != 0):
                    print("window:\t" + str(wind_dict))
                    print("desec_tmp:\t" + tmp)
                    valid -= 1

        return result



S = Solution()
# s = "abc"
# p = "abc"
# s = "abacbabc"
# p = "abc"

s = "cbaebabacd"
p = "abc"

print(S.findAnagrams(s,p))