567. Permutation in String
- 我們需要想的是窗口增大的時候,需要更新哪些資訊?
- 如果 char 在目標內,增加計數
- 如果 char 的計數已經達到目標的計數,valid 加一
- 何時要收縮窗口?
- 如果窗口的字串的長度已經大於目標的字串(因為我們要找的是 permutation)
- 收縮窗口時,需要更新哪些資訊?
- 檢查左邊的指針的字元在目標內
- 如果 char 的計數已經達到目標的計數,valid 減一
- 如果 char 在目標內,減少
- 最終結果要在「擴大窗口」時更新還是「收縮窗口」時更新?
- 如果 valid 剛好和 target 的長度一樣的時候,代表找到 permutation 了,回傳 True
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
target = Counter(list(s1))
visited = defaultdict(int)
left = 0
right = 0
valid = 0
while right < len(s2):
char = s2[right]
right += 1
if char in target:
visited[char] += 1
if visited[char] == target[char]:
valid += 1
while right - left >= len(s1):
if valid == len(target):
return True
char = s2[left]
left += 1
if char in target:
if visited[char] == target[char]:
valid -= 1
visited[char] -= 1
return False