很复杂的题目,无论是思路还是实践都很难…
思路还是看了答案(?)设定两个指针“框”出一串字符串,初始两个指针都指在s的零位,先移动下指针,直到使框出的字符串中包含t中所有字符串,接着移动上指针,一直到不能框出包含全部t中字符串为止,记录上下指针框住的字符串,接着再移动下指针……如此循环,直到下指针出界为止。
class Solution {
public:string minWindow(string s, string t) {int m=s.size()-1;int n=t.size()-1;int tt[52];for(int i=0;i<=n;i++){if(t[i]>91) tt[t[i]-97]++;else tt[t[i]-65+26]++;}string result(s);int up=0;int down=-1;int ss[52];bool b=1;bool pd=0;while(1){while(b==1){b=0;down++;for(int i=0;i<26;i++){if(s[down]==i+97) ss[i]++;if(ss[i]<tt[i]) b=1;}for(int i=26;i<52;i++){if(s[down]==i+65-26) ss[i]++;if(ss[i]<tt[i]) b=1;}if(b==1&&down==m){if(pd==0) return "";else return result;}}while(b==0){for(int i=0;i<52;i++){if(i<26&&s[up]==i+97) ss[i]--;if(i>25&&s[up]==i+65-26) ss[i]--;if(ss[i]<tt[i]) b=1;}up++;}if(down-up+1<result.size()){result=s.substr(up-1,down-up+2);pd=1;}if(down>=m) break;}return result;}
};