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
记得按表情符号拿身分组