LeetCode 筆記 - 567. Permutation in String

題目在此 567. Permutation in String

給定兩個字串,請判斷 s1 的所有排列組合,是否有出現在 s2 裏面

解題思維

基本思維是不計算所有排列組合,而是使用 Counter 計算字串的所有字母個數

加上 Sliding Window 來檢查即可。

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:

size1 = len(s1)
size2 = len(s2)

counter1 = collections.Counter(s1)
cur_counter = collections.Counter(s2[:size1])

if counter1 == cur_counter:
return True

for i in range(1, size2 - size1 + 1):
cur_counter[s2[i - 1]] -= 1
if cur_counter[s2[i - 1]] == 0:
del cur_counter[s2[i - 1]]

cur_counter[s2[i + size1 - 1]] += 1

# print(cur_counter)
if counter1 == cur_counter:
return True

return False

也許你也會想看看