LeetCode 筆記 - 567. Permutation in String

Posted on 標籤
判定字串 s1 的排列組合是否出現在 s2 中。本文捨棄窮舉所有排列，轉而利用滑動視窗（Sliding Window）配合計數器（Counter）追蹤字元出現頻率。這種策略能大幅降低計算成本，在線性時間內完成子字串的頻率比對。
⚠️ 舊文提醒：本文發佈於約 4 年前，部分內容或指令可能已過時，請斟酌參考。

題目在此 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

也許你也會想看看