MENU

LeetCode76. Minimum Window Substring(滑动窗口)

2019 年 02 月 14 日 • 阅读: 1136 • LeetCode阅读设置

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日 星期四