在解决最小覆盖子串一类问题时,通常的思路是先在原字符串中找到目标字符串所包含的所有字符,然后逐步缩小窗口,直到窗口中的字符不再包含目标子串中的字符。这个过程中记录子串的开始位置和长度。
string MinWindow(string s, string t)
{
unordered_map<char, int> need, window;
for(char i : t) {
need[i]++;
}
int left = 0;
int right = 0;
int valid = 0;
int start = 0;
int len = INT32_MAX;
while(right < s.size()) {
char c = s[right];
right++;
if (need.count(c) > 0) {
window[c]++; // 加入滑窗
if (window[c] == need[c]) {
valid++;
}
}
while(valid == need.size()) {
if (right -left < len) {
start = left;
len = right - left;
}
char d = s[left];
left++;
if (need.count(d)) {
if (window[d] == need[d]) {
valid--;
}
window[d]--; // 从滑窗删除
}
}
}
return len == INT32_MAX ? "" : s.substr(start, len);
}
1、对于子串覆盖类问题,抓住一点,目标子串的特征是a,有哪些字符;b,这些字符中每个字符有几个。转换为统计特征后,字符之间的先后顺序则通过双指针的移动来表示,因为双指针的移动不改变字符串中各字符的先后顺序。
2、滑动窗口的构造即抓住1中所述的特点构造Hash表,字符作为key。字符入窗和出窗的操作即改变Hash表中对应字符的value。
3、滑动窗口中的双指针均是从左往右移动。