Day13-字符串-最小窗口子串
一 唠嗑？
今天这道题花我时间xue微有点长，就不唠嗑了，还得赶需求呢
周末的文章再给大家唠嗑
二 上题了
Q：已知字符串S和字符串T，求在S中的最小窗口（区间），使得这个区间包含了T的所有字符
举例：S = “ADOBECODEBANC”， T = “ABC”
包含T的子区间，有“ADOBEC”， “CODEBA”， “BANC”
其中BANC最短，那么我们返回BANC
三 冷静分析
此时你脱口而出：枚举S的所有字符串，满足T的同时，再满足最短！
那么这次面试大概就是重在参与了
其实字符串问题，和哈希表，哈希map结合的同时，一个很重要的思想便是滑动窗口。用它的好处就是只用遍历一遍字符串，O（N），面试官怎么也挑不出来你，况且题目中都提到了最小窗口，那何乐而不为呢
好的，不BB了，这样处理逻辑：
1.建立两个字符哈希，map_s, map_t, map_s代表当前处理的窗口区间里的字符数量，map_t代表字符串T的字符个数
2.两个指针，i，begin，都指向第一个字符
3.i指针逐个向后遍历S中字符，每次都检查是否需要移动begin
当begin指向的字符，T中压根没有，直接后移begin；
当begin指向的字符，T中有，但是当前窗口中该字符数量多了，那么就代表我们需要调整窗口，则后移begin，同时更新map_s中字符的个数
其他情况均不用移动begin
i指针每遍历一个字符，均检查一下是否可以更新最终结果
整个过程中，使用begin与i维护一个窗口，该窗口的子串满足条件，窗口线性向前滑动，时间复杂度O（N）
四 完整代码及注释
//
// Created by renyi on 2019/6/19.
//
#include <iostream>
#include <string>
#include <vector>
using namespace std;
bool is_window_ok(int map_s[], int map_t[], 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;//遍历t中的字符，如果此时s中该字符的数量，比t中该字符的数量还要少，就不满足窗口条件了
}
}
return true;
}
string minWindowSubString(string s, string t){
int map_s[128] = {0};//利用0~127的数组下标来记录字符个数，记录字符串s中各字符的数量
int map_t[128] = {0};//记录t的各字符数量
vector<int> vec_t;
for (int i = 0; i < t.length(); i++) {
map_t[t[i]]++;//记录字符串t中各字符数量
}
for (int i = 0; i < 128; i++) {
if (map_t[i] > 0){
vec_t.push_back(i);//记录字符串t中，都有哪些字符
}
}
int begin = 0;
string result;
for (int i = 0; i < s.length(); i++) {
map_s[s[i]]++;
while (begin < i){
char begin_char = s[begin];
if (map_t[begin_char] == 0){//即，s的begin下标对应的字符，根本不在t中，直接begin后移
begin++;
}
else if (map_s[begin_char] > map_t[begin_char]){//s的当前字符比t的多，即不需要那么多，将begin后移，当前字符数量减1
map_s[begin_char]--;
begin++;
}
else {
break;//其他情况均不用移动begin的位置
}
}
if (is_window_ok(map_s, map_t, vec_t)){
int new_window_len = i - begin + 1;//新窗口字符串的长度
if (result == "" || result.length() > new_window_len){
result = s.substr(begin, new_window_len);
}
}
}
return result;
}
int main(){
string string1 = "ADOBECODEBANC";
string result = minWindowSubString(string1, "AC");
printf("%s\n", result.c_str());
return 0;
}运行结果
将T改成“ABC”
int main(){
string string1 = "ADOBECODEBANC";
string result = minWindowSubString(string1, "ABC");
printf("%s\n", result.c_str());
return 0;
}运行结果
逻辑稍微有点繁琐，动手实现一下吧