Re: [閒聊] 每日LeetCode已回收
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
推
02/04 10:27,
2年前
, 1F
02/04 10:27, 1F
→
02/04 10:31,
2年前
, 2F
02/04 10:31, 2F
推
02/04 10:32,
2年前
, 3F
02/04 10:32, 3F
→
02/04 10:34,
2年前
, 4F
02/04 10:34, 4F
推
02/04 10:35,
2年前
, 5F
02/04 10:35, 5F
推
02/04 10:41,
2年前
, 6F
02/04 10:41, 6F
→
02/04 10:42,
2年前
, 7F
02/04 10:42, 7F
推
02/04 11:18,
2年前
, 8F
02/04 11:18, 8F
推
02/04 12:51,
2年前
, 9F
02/04 12:51, 9F
討論串 (同標題文章)
完整討論串 (本文為第 216 之 719 篇)：