给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 "" 。
注意:如果 s 中存在这样的子串,我们保证它是唯一的答案。
输入:s = "ADOBECODEBANC", t = "ABC"
输出:"BANC"
滑动窗口,left和right一起从0出发。
right右移,直到left到right范围内完整包含了t子串的每个字符(isfulll=true)。
此时,left向右收紧,直到isfulll=false,此时[left-1,right]里完整匹配了t,但不能停下,因为它可能不是最短的。
right继续向右移动,isfull满足时再缩紧left,直到right走到尽头。
每次比较[left-1,right]子串长度是不是当前最短的,打擂台,如果是,保存入left_min和right_min。
判断t中所有字符都有匹配的方式是使用哈希表,提前将对应的字符设置为负数,一旦匹配成就+1。
class Solution { public: string minWindow(string s, string t) { map<char,int> mymap; for(auto i:t) mymap[i]--;//负数表示待匹配 int left=0,right=0; int left_min=0,right_min=-1,min_length=100000;//min存最小子串的开头和结尾,-1是适用空字符串情况 while(right<s.length()){ if(mymap.count(s[right])) mymap[s[right]]++;//每匹配到一个加1 if(isfull(mymap)){//right移动到已经全部匹配时,left开始向右收紧 while(left<=right&&isfull(mymap)){ if(mymap.count(s[left])) mymap[s[left]]--; left++; }//此时[left-1,right]里完整匹配了t,但不能停下,因为它可能不是最短的 if(right-left+2<min_length) { min_length=right-left+2; right_min=right; left_min=left-1; } } right++; } string ans=""; for(int i=left_min;i<=right_min;i++){ ans+=s[i]; } return ans; } //利用哈希表存储t的每个字符是否都已被匹配,设置负数也是因为可能有重复字母 bool isfull(map<char,int>& mymap){ for(auto i=mymap.begin();i!=mymap.end();i++) if(i->second<0) return false;//如果还有负数存在,说明还有的未被匹配 return true; } };