接外包,有相关需求的可以联系我:Telegram | Email

Find All Anagrams in a String | Sliding Windows

该文章创建(更新)于02/26/2022,请注意文章的时效性!

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".

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))


👇 Share | 分享 👇


要不赞赏一下?

微信
支付宝
PayPal
Bitcoin

版权声明 | Copyright

除非特别说明,本博客所有作品均采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可。转载请注明转自-
https://www.emperinter.info/2022/02/26/find-all-anagrams-in-a-string/


要不聊聊?

我相信你准备留下的内容是经过思考的!【勾选防爬虫,未勾选无法留言】

*

*



微信公众号

👉 NewsLetter ❤️ 邮箱订阅 👈

优惠码