76 Minimum Window Substring
https://leetcode.com/problems/minimum-window-substring/#/description
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).
For example,
S="ADOBECODEBANC"
T="ABC"
Minimum window is"BANC".
Note:
If there is no such window in S that covers all characters in T, return the empty string"".
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
分析及代码
discuss有一种解法真的是太赞了，还给了一系列关于substring的general解法。
这题的c++代码是：
string minWindow(string s, string t) {
vector<int> map(128,0);
for(auto c: t) map[c]++;
int counter=t.size(), begin=0, end=0, d=INT_MAX, head=0;
while(end<s.size()){
if(map[s[end++]]-->0) counter--; //in t
while(counter==0){ //valid
if(end-begin<d) d=end-(head=begin);
if(map[s[begin++]]++==0) counter++; //make it invalid
}
}
return d==INT_MAX? "":s.substr(head, d);
}
Java是
public String minWindow(String s, String t) {
int[] map = new int[128];
int len = t.length();
//统计template里面字母的次数
for(int i = 0; i < len; i++) {
map[t.charAt(i)]++;
}
int minLen = Integer.MAX_VALUE;
int minStart = 0;
int start = 0;
int end = 0;
int cnt = len;
while(end < s.length()) {
//对于非关键字母，对它的map里的计数-1
//所以map里面的计数，如果是非关键字母，那么一定是小于或者等于零的，只有关键字母会大于0
if(map[s.charAt(end++)]-- > 0) {
cnt--;
}
//cnt == 0是所有关键字母都已经得到的情况，要做的是，从头开始退格，一直退到无法保持关键字母都存在的状况
//退格要做的是：1.map相对的位置+1；2.向后移动start
//如果退掉的是一个关键字母(因为此位非负)，并且是一旦退掉这个就无法保持关键字母都在的状况(因为==0，而不是>0)
//那么cnt++
while(cnt == 0) {
if(end - start < minLen) {
minLen = end - start;
minStart = start;
}
if(map[s.charAt(start++)]++ == 0) {
cnt++;
}
}
}
//记得判断无法找到的情况
return minLen == Integer.MAX_VALUE? "": s.substring(minStart, minStart + minLen);
}
简直棒呆。
还给了一个general的模板，可以做substring相关的题目
int findSubstring(string s){
vector<int> map(128,0);
int counter; // check whether the substring is valid
int begin=0, end=0; //two pointers, one point to tail and one head
int d; //the length of substring
for() { /* initialize the hash map here 初始化，比如计数之类的*/ }
while(end<s.size()){
if(map[s[end++]]-- ?){ /* modify counter here 改变cnt计数*/ }
while(/* counter condition */){
/* update d here if finding minimum*/
//increase begin to make it invalid/valid again
if(map[s[begin++]]++ ?){ /*modify counter here*/ }
}
/* update d here if finding maximum*/
}
return d;
}
相关的题目，真的是一看就懂，包教包会包融会贯通：
- [3. Longest Substring Without Repeating Characters]
原题连接：https://leetcode.com/problems/longest-substring-without-repeating-characters/\#/description
GitBook连接：
- [Longest Substring with At Most Two Distinct Characters]()
原题连接：https://leetcode.com/problems/longest-substring-without-repeating-characters/\#/description
GitBook连接：