题意：给你一个字符串 S、一个字符串 T 。请你设计一种算法，可以在 O(n) 的时间复杂度内，从字符串 S 里面找出：包含 T 所有字符的最小子串。
思路：这题要求O(n)的复杂度，首先想到用两个指针i,j遍历S串，找到满足条件的(j - i + 1)的最小值。问题在于怎么在O(1)的复杂度内判断S[i,j]包含T中所有的字符呢？
用一个mp数组记录T串中所有字符出现的次数，字符的ASCII码作为下标。（一开始以为只有大写字母，直接用字符-‘A’作为下标了）。并且统计T串中不同字符的个数cnt。
在遍历S串的时候，实时统计每个字符出现的次数，如果某个字符出现的次数等于mp[i]，那么sum++，如果sum==cnt，说明这时候S[i,j]包含T串中所有字符的个数。i往后移，直到sum != cnt。
小小的剪枝：如果当前已经有满足条件的子串，并且j-i+1要比满足条件的子串的长度要长，i往后移，注意更新每个字符出现的次数。
C++代码：
class Solution {
public:
int mp[200];
string minWindow(string s, string t) {
if(s.size() == 0 || t.size() == 0) return "";
memset(mp, 0, sizeof(mp));
int cnt = 0;
for(int i = 0; i < t.size(); i++){
if((int)mp[t[i]] == 0) cnt++;
mp[(int)t[i]] += 1;
}
int i = 0, j = 0;
int reslen = -1;
int resstart = -1;
int tmp[200];
int sum = 0;
memset(tmp, 0, sizeof(tmp));
while(i < s.size() && j < s.size()){
if(reslen != -1 && j - i + 1 > reslen){
int id2 = (int) s[i];
if(mp[id2]){
if(tmp[id2] == mp[id2]){
sum--;
}
tmp[id2]--;
}
i++;
continue;
}
int id = (int)s[j];
if(mp[id]){
tmp[id]++;
if(tmp[id] == mp[id]){
sum ++;
}
}
if(sum == cnt){
if(reslen == -1 || reslen > j - i + 1){
resstart = i;
reslen = j - i + 1;
}
while(i < j){
int id2 = (int)s[i];
if(mp[id2]){
tmp[id2]--;
if(tmp[id2] < mp[id2]){
i++;
sum--;
break;
}
}
i++;
if(reslen > j - i + 1){
reslen = j - i + 1;
resstart = i;
}
}
}
j++;
}
if(reslen == -1) return "";
return s.substr(resstart, reslen);
}
};
/*
"ABABABABAABABAAA"
"AAA"
*/
网友评论