Re: [閒聊] 每日LeetCode

[pandix (麵包屌)]

567. Permutation in String

給你兩個字串 s1 和 s2，問你有沒有 s1 的某個 permutation 是 s2 的 substring


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

Example 2:
Input: s1 = "ab", s2 = "eidboaoo"
Output: false


思路:
1.當然不能列出所有 permutations 然後一個一個檢查他們是不是在 s2 裡

這邊可以用字母出現的次數去比較

如果 s2 中的某一段 Counter() 和 Counter(s1) 完全相同

那就知道說這一段就是 s1 的某個 permutation


2.由於要的是 substring 就用老方法 2-pointer 維護左界右界

如果加進右界後不合法 就推進左界直到合法

不合法就是右界加的字母 c 讓目前該字母的數量超過 Counter(s1)[c] 了

這時候就推進左界並且把左界的字母數量減一

最後再想個辦法快速比較目前的 Counter() 是不是完全等於 Counter(s1)

其實可以直接比右界減左界的長度有沒有等於 len(s1) 就好

Python code:
class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        count1 = Counter(s1)
        count2 = Counter()
        n1 = len(s1)
        left = 0
        for i, c in enumerate(s2):
            count2[c] += 1
            while count2[c] > count1[c]:
                count2[s2[left]] -= 1
                left += 1

            if n1 == i - left + 1:
                return True

        return False


有人在問再貼一次 https://discord.gg/BsYNc9nE

記得按表情符號拿身分組


--

蛤?

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.251.194.165 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1675477541.A.801.html
推 rockyao: 完全看無
→ pandix: 哪裡 我嘗試寫詳細一點
推 rockyao: 我三類的 看無
→ pandix: 你是三類大師==
推 surimodo: 有色圖 好評
推 SecondRun: 大師
→ SecondRun: 原來是你在推廣
推 a9101214: 大師
推 Rushia: 大師