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

Permutation in String

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

Desciption

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1's permutations is the substring of s2.

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

Thought

Slide Window

Code

  • submit code
class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        need_dict = {}
        need_count = 0
        # 需求字典创建
        for i in s1:
            need_dict[i] = need_dict.get(i,0) + 1
            need_count += 1

        window_list = {}


        right = 0
        left = 0
        valid = 0

        while right < len(s2):
            c = s2[right]
            right += 1

            if(need_dict.get(c,0) > 0):
                window_list[c] = window_list.get(c,0) + 1
                if(window_list.get(c) == need_dict.get(c)):
                    valid += 1

            while(right - left >= len(s1)):
                if(valid == len(need_dict)):
                    return True

                d = s2[left]
                left += 1

                if(need_dict.get(d)):
                    if(need_dict.get(d) == window_list.get(d,0)):
                        valid -= 1
                    window_list[d] = window_list.get(d) - 1

        return False
  • full code
class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        need_dict = {}
        # 需求字典创建
        for i in s1:
            need_dict[i] = need_dict.get(i,0) + 1

        window_list = {}


        right = 0
        left = 0
        valid = 0

        while right < len(s2):
            c = s2[right]
            # print("c"+c)
            right += 1

            if(need_dict.get(c)):
                window_list[c] = window_list.get(c,0) + 1
                if(window_list.get(c) == need_dict.get(c)):
                    valid += 1

            while(right - left >= len(s1)):

                if(valid == len(need_dict)):
                    return True

                d = s2[left]
                left += 1

                if(need_dict.get(d)):
                    if(need_dict.get(d) == window_list.get(d,0)):
                        valid -= 1
                    window_list[d] = window_list.get(d) - 1

        return False


S = Solution()
# s1 = "ab"
# s2 = "eidbaooo"
s1 = "abcdxabcde"
s2 = "abcdeabcdx"

print(S.checkInclusion(s1,s2))


👇 Share | 分享 👇


要不赞赏一下?

微信
支付宝
PayPal
Bitcoin

版权声明 | Copyright

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


要不聊聊?

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

*

*



微信公众号

👉 NewsLetter ❤️ 邮箱订阅 👈

优惠码


阿里云国际版20美元
Vultr10美元
搬瓦工 | Bandwagon应该有折扣吧?
域名 | namesiloemperinter(1美元)