返回

[Leetcode]76. Minimum Window Substring(C++)

题目描述

题目链接:76. Minimum Window Substring

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).

例子

Input: “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.

解题思路

这道题目是比较典型的使用滑动窗口的题目。我们用一对指针 frontback定义一个滑动窗口。首先通过一个哈希表 record 记录 T 中的字符及次数,并用一个变量 to_match 来表示我们当前还需要匹配的单词的个数。

接下来让 back 往后遍历进行滑动窗口的扩张,对每一位字符进行检查:

  • 如果字符在 record 中并且次数大于 0,则表示是我们需要匹配的字符,所以 to_match 减一
  • record 中对当前字符的次数减一
  • to_match == 0 时,表示我们已经找到所有需要匹配的字符了,这个时候移动 front 来进行滑动窗口的压缩
    • 首先判断是否比当前最短结果短,如果是则更新结果
    • record 中对 front 指向的字符 c 加一
    • 如果 record[c] > 0,表示我们又有需要匹配的字符了,对 to_match 加一,跳出循环
    • 否则继续压缩

代码如下:

#include <string>
#include <unordered_map>
#include<bits/stdc++.h>

class Solution {
public:
    std::string minWindow(std::string s, std::string t) {
        std::unordered_map<char, int> record;
        for (char c: t) record[c]++;
        int begin = 0;              // final string begin index
        int final_length = INT_MAX; // final string length
        int to_match = t.length();  // character to be matched

        int front = 0, back = 0;    // two-pointer defining sliding window

        while (back < s.length()) { // expanding sliding window

            if (record[s[back]] > 0) {  // target char
                to_match--;
            }

            record[s[back]]--;

            while(to_match == 0) {  // now we have all needed chars in sliding window, so compress it
                int len = back - front + 1;
                if (len < final_length) {   // if current substr is shorter update final result
                    final_length = len;
                    begin = front;
                }
                record[s[front]]++;
                if (record[s[front]] > 0) to_match++;
                front++;
            }

            back++;
        }

        return final_length == INT_MAX ? "" : s.substr(begin, final_length);

    }
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

GitHub 代码同步地址: 76.MinimumWindowSubstring.cpp

其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions

Built with Hugo
Theme Stack designed by Jimmy