最小窗口子串
已知字符串S与字符串T，求在S中的最小窗口(区间)，使得这个区间中包含 了字符串T中的所有字符。 例如: S = “ADOBECODEBANC” ;T = "ABC " 包含T的子区间中，有“ ADOBEC”， “CODEBA”， “BANC” 等等;最小窗口 区间是 “BANC” LeetCode 76. Minimum Window Substring
枚举 S = “ADOBECODEBANC” 的所有子字符串:
bool is_window_ok(int map_s[], int map_t[], std::vector<int> &vec_t){
for(int i = 0; i < vec_t.size(); i++){
if(map_s[vec_t[i]] < map_t[vec_t[i]]){
return false;
}
}
return true;
}
int main(){
std::string s= "ADOBECODEBANC";
std::string t = "ABCDAB";
const int MAX_ARRAY_LEN = 128;// char 0-127
int map_t[MAX_ARRAY_LEN] = {0};//记录t字符串各字符个数
int map_s[MAX_ARRAY_LEN] = {0};
std::vector<int> vec_t;//记录t字符中有哪些字符
for(int i = 0; i < s.length(); i++){
map_s[s[i]]++;
}
for(int i = 0; i< t.length(); i++){
map_t[t[i]] ++;
}
for(int i =0 ;i < MAX_ARRAY_LEN; i++){
if( map_t[i] > 0){
vec_t.push_back(i);
}
}
}1.设置两个字符哈希数组，map_s与map_t，map_s代表当前处理的窗口区间中的字符数量， map_t代表子串T的字符数量。 2.设置两个指针(记作指针i与指针begin)指向字符串第一个字符; 3.i指针向后逐个扫描字符串中的字符，在这个过程中，循环检查begin指针是否可以向前移动: 如果当前begin指向的字符T中没出现，直接前移begin; 如果begin指向的字符T中出现了，但是当前区间窗口中的该字符数量足够，向前移动begin，并更 新map_s; 否则不能移动begin，跳出检查。 4.指针i每向前扫描一个字符，即检查一下是否可以更新最终结果(找到最小的包含T中各个字符的窗口)。 在整个过程中，使用begin与i维护一个窗口，该窗口中的子串满足题目条件(包含T中所有字符)， 窗口线性向前滑动，整体时间复杂度为O(n)。
int window_begin = 0;
std::string result;
for(int i = 0; i < s.length(); i++){
map_s[s[i]]++;
while(window_begin < i){
char begin_ch = s[window_begin];
if(map_t[begin_ch] == 0){
window_begin ++;
}
else if(map_s[begin_ch] > map_s[begin_ch]){
map_s[begin_ch]--;
window_begin++;
}
else{
break;
}
if( is_window_ok(map_s, map_t,vec_t)){
int new_window_len = i - window_begin +1;
if( result == "" || result.length() > new_window_len){
result = s.substr(window_begin,new_window_len)
}
}
return result;
}
};本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018.05.10 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读