76.Minimum Window Substring
问题:给出两个字符串,求第一个字符串中包含第二个字符串的最大子串。
思路:建立两个hash表。第一个hash表存储第二个字符串中各个字符出现的次数。第二个hash表初始化跟第一个hash相同,只不过各个字符的value都等于0。然后遍历第一个字符串,只要当前字符出现在第一个hash表中,就将第二个hash的对应字符的value加1,直到第二个hash表中所有字符的value都大于等于第一个hash表,此时找到了第一个可行解的right。
用双指示left和right表示窗口的左右边界。找到第一个可行解的right之后,此时固定right,移动left,直到“第二个hash表恰好满足所有value大于等于第一个hash表value”,此时的left和right就是第一个可行解,看情况判断是否更新窗口大小。这样一直进行,知道right超出边界。
class Solution {
public:
string minWindow(string s, string t) {
int s_len=s.size();
int t_len=t.size();
if(s_len == 0 || s_len<t_len) return string("");
//two hash
unordered_map<char,int> dict;
unordered_map<char,int> s_dict;
for(int i=0;i<t_len;i++){
if(dict.count(t[i])){
dict[t[i]]++;
}else{
dict[t[i]]=1;
s_dict[t[i]]=0;
}
}
int left=0;
int right=0;
int distinct_char_num=0;//当前第二个hash表中已经集齐多少个t的字符
int min_left=0;
int min_right=s_len-1;
bool find_flag=0;//判断是否有解
while(right<s_len){
//右边界移动
while(right<s_len && distinct_char_num!=t_len){
if(dict.find(s[right])!=dict.end()){
s_dict[s[right]]++;
if(s_dict[s[right]]<=dict[s[right]]){
distinct_char_num++;
if(distinct_char_num==t_len){
find_flag=1;
break;
}
}
}
right++;
}
//已经找不到可行解了。
if(right>=s_len) break;
//左边界移动
while(left<=right && distinct_char_num==t_len){
if(dict.find(s[left])!=dict.end()){
s_dict[s[left]]--;
if(s_dict[s[left]]<dict[s[left]]){
//更新最小窗口
if((min_right-min_left)>(right-left)){
min_right=right;
min_left=left;
}
distinct_char_num--;
left++;
break;
}
}
left++;
}
right++;
//---------------
}
if(find_flag)
return s.substr(min_left,min_right+1-min_left);
else
return string("");
}
};