題目描述:給定兩個字串 s1 和 s2,判斷 s2 中是否包含 s1 的任意一個排列(permutation)作為子字串。換句話說,判斷 s2 是否有一個長度與 s1 相同的連續子字串,其字元組成與 s1 完全相同(不計順序)。
解題思路:這道題是經典的**固定大小滑動視窗(Sliding Window)**問題。
s1 的任意排列都具有相同的字元頻率。因此,問題轉化為:s2 中是否存在一個長度為 s1.length() 的子字串,其字元頻率與 s1 完全相同。
演算法:
s1 的字元頻率統計(大小為 26 的陣列)。s1.length() 的滑動視窗在 s2 上移動,維護視窗內的字元頻率。s1 的頻率陣列相同,回傳 true。優化:維護一個 matches 計數器(0~26),記錄頻率已匹配的字元種類數。每次視窗移動時更新 matches,當 matches == 26 時表示完全匹配,避免每步都做陣列比較(O(26) → O(1) per step)。
時間複雜度:O(n) — 其中 n 為 s2 的長度。滑動視窗每個字元最多被加入和移除各一次,每步的視窗更新操作為 O(1)(只需更新單一字元頻率和 matches 計數器)。初始化階段為 O(26 + |s1|),可視為常數。
空間複雜度:O(1) — 使用兩個大小固定為 26 的陣列儲存字母頻率,空間與輸入大小無關。
1. If len(s1) > len(s2): return false 2. Build count1[26] for s1, count2[26] for first window of s2 (size = len(s1)) 3. Count initial matches = number of indices i where count1[i] == count2[i] 4. Set l = 0 5. For r from len(s1) to len(s2) - 1: a. If matches == 26: return true b. Add s2[r] to window: increment count2[s2[r]], update matches c. Remove s2[l] from window: decrement count2[s2[l]], update matches d. l++ 6. Return matches == 26
直接陣列比較滑動視窗 O(26n):同樣使用滑動視窗,但每次視窗移動後直接比較兩個長度為 26 的頻率陣列是否相等,時間複雜度為 O(26n)。實作更直觀,但引入 O(26) 的常數因子。
排序比較 O(n × |s1| log |s1|):對 s1 排序,然後枚舉 s2 的每個長度為 |s1| 的子字串並排序比較。時間複雜度遠高於滑動視窗法,僅適合理解題意時的暴力解。
s2 中所有 s1 排列的起始索引」(LeetCode 438 Find All Anagrams in a String),如何修改上述演算法?matches 優化技巧(避免每步比較整個頻率陣列)的本質是什麼?是否可以推廣到其他需要頻繁比較計數的問題?