LeetCode76. Minimum Window Substring（滑动窗口）

LeetCode76. Minimum Window Substring（滑动窗口）

• Hard
• Accepted：207,009
• Submissions：698,439

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Note:

• If there is no such window in S that covers all characters in T, return the empty string "".
• If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

---

链接

https://leetcode.com/problems/minimum-window-substring/

题意

给定字符串S和字符串T，在S中找到包含T所有字符的最短子串（窗口），复杂度为$O(n)$，没有则返回空字符串。

题解

• 按照题目要求，我们可以使用滑动窗口解决这个问题，之前一个类似的题目是：LeetCode438. Find All Anagrams in a String，它的要求是再s中找p，和本题的区别是要求长度相等和最小起始位置
• 首先解决匹配问题，还是使用一个计数数组记录字符串T中所有的字符，然后在S中遇到一个就减减，直至和T中所有的字符都完成匹配。
• 在窗口的滑动过程中，如果要求长度与T相同时那么遍历到了T的长度时左指针就开始滑动，而不要求相等时我们需要每次完成匹配后再移动左指针开始右移，并且更新最小长度，注意两者区别。
• 详细过程可以参考：传送门

代码

• Runtime: 12 ms, faster than 99.60% of C++ online submissions for Minimum Window Substring.
• Memory Usage: 9.7 MB, less than 100.00% of C++ online submissions for Minimum Window Substring.

class Solution {
public:
    string minWindow(string s, string t) {
        int cnt[256] = {0};
        int n = s.length(), m = t.length();
        int ans = n + 1, start = 0;
        int l = 0, r = 0, tot = m;
        for (int i = 0; i < m; ++i) // 记录T中每个字符
            cnt[t[i]]++;
        // 滑动窗口S[l, r) 左闭右开
        while (r < n)
        {
            if (cnt[s[r++]]-- > 0) // 匹配单个字符
                --tot;
            while (tot == 0) // 完成一次匹配
            {
                if (ans > r - l) // 更新答案最小长度
                {
                    ans = r - l; // 长度
                    start = l; // 起始位置
                }
                if (cnt[s[l++]]++ > -1) // 左指针开始右移
                    ++tot;
            }
        }
        if (ans == n + 1) // 没有找到返回空字符串
            return "";
        return s.substr(start, ans);
    }
};

---

The end.
2019年2月14日 星期四