[Leetcode解題] 567. Premutation in String

23 December 2023
medium two-pointers hashmap

題目

567. Premutation in String

給定兩個字串s1與s2，判斷s2中是否包含s1其中一種排列組合的子字串

解題思路

假設s1的長度為 $n$ ，s2的長度為 $m$，直覺從暴力法想起，我們可以直接窮舉所有s1的排列組合，並判斷每種組合是否出現在s2中

判斷一個字串A是否出現在字串B可以透過kmp-algorithm達到達到時間複雜度 $O(n+m)$ ，所以暴力法求解的複雜為 $O(n^3+n^2m)$ ，非常高

我們可以想像，暴力法的過程會有許多重複的判斷發生，並不是我們樂見的，舉例來說

考慮此兩種組合，只在前兩個字元交換，後面字串都是一樣的，但卻會進行許多重複的匹配判斷 AB(xxxxxxxxxxx) BA(xxxxxxxxxxx)

因此，我們想到可以透過hashmap來表達一個字串的所有排列組合，因為如果是考慮任一排列組合的話，表達字串內的字元可以任意排列，不具順序性

舉例來說，字串abcd，可以表達成{'a': 1, 'b': 1, 'c': 1, 'd': 1}

再透過雙指針來解，我們定義前指針為head，後指針為tail，只要兩指針之間的字元可以得到相同的hashmap即表達s2包含s1的其中一種排列組合

雙指針的進行為，一開始head和tail皆指在0，依據下列各種狀況運行

  1. 只要tail所指字元出現在hashmap，且數量不為0，則tail指針可繼續往前指
  2. 若tail所指字元出現在hashmap，但數量為0，我們開始移動head，直到該字元的數目不為0方得以繼續移動tail(最壞的情形是head移動到tail的位置)
  3. 若tail所指字元不出現在hashmap，表示我們要從該字元後面開始比對，因此直接移動head到tail的位置，並且從下一個位置進行比對

這邊我們注意，移動tail會消耗hashmap字元的數目，移動head則會加回hashmap字元的數目

另外補充第二點，為什麼最壞的情況是head移動到tail的位置呢? 因為若所指字元出現在hashmap中表達其原始數目至少大於0，當head移動到tail時，hashmap會還原成原始的狀態，所以一定不為零

實作

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2):
            return False
        
        d = {}
        for c in s1:
            d.setdefault(c, 0)
            d[c] += 1

        head = 0
        tail = 0
        val = len(s1)
        while tail < len(s2):
            if s2[tail] not in d:
                # Reset, starting from the next position
                while head < tail:
                    d[s2[head]] += 1
                    head += 1
                    val += 1
                tail += 1
                head += 1
            else:
                if d[s2[tail]] == 0:
                    while head < tail and d[s2[tail]] == 0:
                        d[s2[head]] += 1
                        head += 1
                        val += 1
                else:
                    d[s2[tail]] -= 1
                    tail += 1
                    val -= 1
                    if not val:
                        return True
        return False

時間複雜度

一開始建立hashmap會遍歷s1，時間複雜度為 $O(n)$ ，之後雙指針的移動，會分別移動head跟tail從頭到尾，故最多為$O(2m)$，查詢hashmap的時間為 $O(1)$ ，總時間複雜度為 $O(m)$ ，因為 $m>=n$