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

题目描述

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.

解题思路

• 如果字符在 `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

Built with Hugo
Theme Stack designed by Jimmy