leetcode 76. 最小覆寫子串

一、題目

給你一個字元串 s 、一個字元串 t 。傳回 s 中涵蓋 t 所有字元的最小子串。如果 s 中不存在涵蓋 t 所有字元的子串，則傳回空字元串 “” 。

輸入：

s = "ADOBECODEBANC", t = "ABC"
           

輸出：

"BANC"
           

二、解法

2.1 滑動視窗

解題思路：本題使用滑動視窗求解，即兩個指針 l 和 r 都是從最左端向最右端移動，且 l 的位置一定在r 的左邊或重合。注意本題雖然在 for 循環裡出現了一個 while 循環，但是因為 while 循環負責移動 l 指針，且 l 隻會從左到右移動一次，是以總時間複雜度仍然是 O(n)。本題使用了長度為 128的數組來映射字元，也可以用哈希表替代；其中 chars 表示目前每個字元缺少的數量，flag 表示每個字元是否在 T 中存在

class Solution {
public: 
    string minWindow(string S, string T) {
    vector<int> chars(128, 0);  // 表示目前每個字元串缺少的數量
    vector<bool> flag(128, false);  // 表示每個字元是否在T中存在
    // 先統計T中的字元情況
    for (int i = 0; i < T.size(); ++i)
    {
        flag[T[i]] = true;
        ++chars[T[i]];
    }

    // 移動滑動視窗，不斷更改統計資料
    int cnt = 0, l = 0, min_l = 0, min_size = INT_MAX;
    for (int r = 0; r < S.size(); ++r)  // r為視窗右邊界，l為視窗左邊界
    {
        if (flag[S[r]]) {  // 如果周遊到T中的字元
            if (--chars[S[r]] >= 0)  // 減少結果中缺少的數量
                ++cnt;  // 統計結果中的字元
        }
        // 若目前滑動視窗已包含T中全部字元
        // 則嘗試将l（左邊界）右移，在不影響結果的情況下獲得最短子字元串
        while (cnt == T.size())
        {
            if (r - l + 1 < min_size) {
                min_l = l;  // 更新最短字串的左邊界
                min_size = r - l + 1; // 更新最短子串的大小
            }
            if (flag[S[l]] &&  // 若縮減的字元含有t中的字元
             ++chars[S[l]] > 0)  // 增加該字元在結果中缺少的數量
                --cnt;
            ++l;
        }
    }
    return min_size > S.size()? "": S.substr(min_l, min_size);  // 提取s中的子串
    }
};
           

複雜度分析

• 時間複雜度：最壞情況下左右指針對 s 的每個元素各周遊一遍，哈希表中對 s 中的每個元素各插入、删除一次，對 t 中的元素各插入一次。每次檢查是否可行會周遊整個 tt 的哈希表，哈希表的大小與字元集的大小有關，設字元集大小為 C，則漸進時間複雜度為O(C⋅∣s∣+∣t∣)

  著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。。

• 空間複雜度：這裡用了兩張哈希表作為輔助空間，每張哈希表最多不會存放超過字元集大小的鍵值對，我們設字元集大小為 C ，則漸進空間複雜度為 O©。