题解 | #最小覆盖子串#

NC28 最小覆盖子串

题意分析：

有字符串S和T，在S中找出包含T的所有字符的最短的子串

示例：S = "XDOYEZODEYXNZ"，T = "XYZ"

S有多个子串包含XYZ，如XDOYEZ，YXNZ等等，其中YXNZ是最小的。

题解一（暴力）：

只要枚举出包含T的所有子串，比较他们的长度，找出最小的那个。

bool check(string T, string S) {
    //检查S是否为t的子串
    map<char, int> m;
    for (int i = 0; i < S.size(); i++) {
        m[S[i]]++;
    }
    for (int i = 0; i < T.size(); i++) {
        if (m[T[i]] > 0)m[T[i]]--;
        else {
            return false;
        }
    }
    return true;
}

string minWindow(string S, string T) {
    if (S.size() < T.size()) return "";
    string ret = S;
    bool flag = false;
    for (int i = 0; i < S.size(); i++) {
        for (int j = T.size(); j <= S.size(); j++) {
            //检查字符串S的字串s[i,i+j]是否覆盖住了字符串T
            if (check(T, S.substr(i, j))) {
                if (ret.size() >= j) {
                    flag = true;
                    ret = S.substr(i, j);
                }
            }
        }
    }
    if (flag == true)
        return ret;
    else {
        return "";
    }
}

以上是一个超时代码。

时间复杂度：,S的所有子串长度一共有个，检查是否覆盖住需要O(n)遍历。

空间复杂度：

题解二：（滑动窗口）

我们在暴力求解的时候，check是否覆盖住有很多重复的检查。假设已经check了一次，下一次check只要检查与上一次不同的部分即可。

我们使用滑动窗口可以很好的比较出两次check字符的不同。

设置两个指针left，right。表示S的子串tmp可由left和right表示，当需要添加元素时候，就将right++，pop元素就left++。

我们用哈希表判断left到right是否完全包含T，动态维护窗口中所有字符以及个数。具体过程如下：

如果新加入的字符是被需要的（指在T里面），那么这个字符加入到窗口中，当窗口中的字符数目和被需要的数目相等时候，匹配度加一。right右移，这里匹配度是window里面的字符与need里面字符相等的数目。

如果新加入的字符不被需要（指不在T里面），right右移

当匹配度等于被需要的字符种类数，说明left-right覆盖到了T的所有字符，并且记录当前的left和right位置，然后就开始向右移动left

如果left位置的字符是被T所需要的，windo所统计的left字符要减一，当窗口中left处的字符数目小于need的字符数目，匹配度减一

如果left位置的字符不是被T所需要的，直接右移即可。
举个例子：

接下来的步骤就是像上面重复的一样

最后返回结果。

string minWindow(string S, string T) {
    int left = 0, right = 0
    //表示窗口左右位置的指针
    int start = 0, minLen = INT_MAX;
    //start 表示最后结果字符串开始位置，minlen表示最后字符串长度，二者可以表示一个字符串
    unordered_map<char, int> need;
    //need的存放字符串T的所有字符统计
    unordered_map<char, int> window;
    //window 存放现有的窗口中出现在need中的字符统计

    for (auto i:T)need[i]++;
    int match = 0;
    //window与need的匹配度

    while (right < S.length()) {
        char c1 = S[right];
        if (need.count(c1)) {
            window[c1]++;
            if (window[c1] == need[c1])match++;
        }
        right++;
        while (match == need.size()) {
            //当匹配度等于need.size(),说明这段区间可以作为候选结果，更新ret
            if (right - left < minLen) {
                minLen = right - left;
                start = left;
            }
            char c2 = S[left];
            if (need.count(c2)) {
                window[c2]--;
                if (window[c2] < need[c2]) match--;
            }
            left++;
        }
    }
    return minLen == INT_MAX ? "" : S.substr(start, minLen);
}

时间复杂度：O(n)

空间复杂度：与T中的字符种类线性相关。