題目網址：https://leetcode.cn/problems/permutation-in-string/

題意：給兩 string s1 和 s2, 若 s2 包含 s1 的排列, 則返回 true。否則, 返回 false。

s1 的排列之一是 s2 的 substring。

注意：substring 為連續的, subsequence 為非連續的

Solution：

想法：利用 Sliding Window, 類似 76. Minimum Window Substring

  • 先不斷地增加 right 來擴大窗口
  • 縮小窗口的時機是窗口大小 ≥ s1.size() 時
  • 當 valid == need.size() 時, 代表窗口中的 substring 為合法的排列

注意：這題是「固定長度」的窗口, 因為窗口每次向前滑動時只會移出一個字元, 故可以把內層的 while 改成 if, 其效果是一樣的

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int left = 0, right= 0;
        unordered_map<char, int> window, need;

        for (const auto& ch : s1) {
            ++need[ch];
        }

        int valid = 0;

        while (right < s2.size()) {
            const char c = s2[right];
            window[c]++;
            ++right;

            if (need.find(c) != need.end() && window[c] == need[c]) {
                ++valid;
            }

            while (right - left >= s1.size()) { // 固定窗口，可以改成 if 判斷
                // 存在排列 substring
                if (valid == need.size()) {
                    return true;
                }

                const char d = s2[left];
                if (need.find(d) != need.end() && window[d] == need[d]) { // 移出前相等
                    --valid;
                }

                --window[d];
                ++left;
            }
        }

        return false;
    }
};
  • time：$O(n1 + n2)$ ➔ 其中 n1、n2 分別為 s1、s2 的長度
    • $O(n1)$：遍歷 s1 計算 need
    • $O(n2)$：s2 中的每個元素最多被遍歷 2 次（left、right）
  • space：$O(1)$ ➔ window、need 長度皆為 $O(26)$