[LeetCode]76. Minimum Window Substring

Problem

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

1
2
3
4
5
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.

给定两个字符串S,T, 在串S中找到包含T串中所有字符的最短子串. 时间复杂度要求O(N).

时间复杂度给定了一个具体的要求.线性时间. 所以暴力破解是不可行的. 要求S的子串包含组成T的所有字符,没有顺序的要求,只要包含就行.T串字符可能会有重复元素存在. 所以使用一个unordered_map哈希表来记录T.

Solution

Analysis

具体做法,就是先记录T的组成.然后遍历S串,找到一个解之后,更新左边界,因为这个解当中可能会存在无关元素,以及重复元素.

最短: 通过一个全局变量,记录当前解的长度,及时更新这个变量,最后找到最终解.

Code

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
class Solution {
public:
string minWindow(string s, string t) {
string result = "";
int left = 0, cnt = 0, min_len = INT_MAX;
unordered_map<char, int> table;//t中字符可能会有重复

for (auto &ch: t)
table[ch]++;

for (int i=0; i< s.size(); i++){
if (--table[s[i]] >= 0)// s[i]是t中一个字符; 无关元素(没有出现过)会变为负数.
cnt++;
// 此时,这个解可能包含若干冗余元素,重复元素
while (cnt == t.size()){//找到一个解
if (min_len > i - left + 1){
min_len = i - left + 1;
result = s.substr(left, min_len);
}
if (++table[s[left]] > 0)// 更新左边界:说明left是t中一个字符,如果不是应该小于等于0
cnt--;
left++;
}

}
return result;
}
};

References

https://www.cnblogs.com/grandyang/p/4340948.html

您的支持就是我更新的最大动力!谢谢!