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
記得按表情符號拿身分組