0%

[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 加一,跳出循环
    • 否则继续压缩

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#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