題目連結:
題目意譯:
給定兩個字串 s1 和 s2,回傳真(True)如果 s2 包含 s1 的一種排列,反之回傳假(False)。
換句話說,回傳真(True)如果 s1 的其中一種排列作為子字串包含於 s2。
限制:
1 ≦ s1.length 、 s2.length ≦ 10 ^ 4
s1 和 s2 由小寫英文字母組成。
範例測資:
範例 1:
輸入: s1 = "ab", s2 = "eidbaooo"
輸出: true
解釋: s2 包含 s1 的一種排列("ba")。
範例 2:
輸入: s1 = "ab", s2 = "eidboaoo"
輸出: false
解題思維:
我們可以利用滑動視窗(Sliding Window)的概念,例如 s1 = "ab" 、 s2 = "eidbaooo":
eidbaooo
掃過兩個字元,發現完全沒有出現 'a' 或是 'b'。
eidbaooo
可以看到這個視窗與上一個只差在開頭與結尾(紅色代表消失的、藍色代表新增的)。所以視窗不論長度多少,也只需要額外判斷這兩個差異的字元即可,不需整個重新統計。
eidbaooo
這邊包含了一個 'b'。
eidbaooo
最後這邊有包含了 'b' 以及 'a'。因此 s2 的其中一個排列包含於 s1 中。
其他情況也是同理。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。