算法思想
- 在字符串 S 中使用双指针的左右指针技巧,初始化 left = right = 0,索引闭区间 [left, right] 称为一个窗口
- 先不断增加 right 指针扩大窗口 [left, right],直到窗口中的字符串符合要求(包含了 T 中的所有字符串)
- 此时,停止增加 right,转而不断增加 left 指针来缩小窗口 [left, right],直到窗口中的字符串不再符合要求 (不包含 T 中的所有字符了)。同时,每次增加 left,都要更新一轮结果。
- 重复 2 - 3 ,直到 right 到达尽头。
框架代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| string s, t; int left = 0,right = 0;
string res = s; while (right < s.size()) { window.add(s[right]) right ++; while (window 符合要求) { res = minLen(res, window); window.remove(s[left]); left++; } } return res;
|
那么我们要如何判断window即子串 s[left...right]
是否符合要求,是否包含 t
的所有字符呢?
可以用两个hash表来做计数器,一个记录t的字符以及出现次数,另一个window则记录当前窗口所包含的字符及出现的次数,如果window包含所有needs中的键,且这些键对应的值都大于等于needs中的值,那么就可以知道当前窗口符合要求了,可以开始移动left
指针。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
| stirng s, t;
int left = 0,right = 0; string res = s;
unordered_map<char, int> window; unordered_map<char, int> needs;
for (char c : t) { needs[c] ++; }
int match = 0;
while (right < s.size()) { char c1 = s[right]; if (needs.count(c1)) { window[c1] ++; if (window[c1] === needs[c1]) { match ++; } } right ++; while (match === needs.size()) { res = minLen(res, window); char c2 = s[left]; if (needs.count(c2)) { window[c2] --; if (window[c2] < needs[c2]) { match --; } } } } return res;
|
lc76 最小覆盖子串
这题可以套一套我们上面的板子:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
|
var minWindow = function (s, t) { s = s.split('') t = t.split('') let tMap = new Map() let window = new Map() let min = Number.MAX_SAFE_INTEGER let start = 0 let l = 0, r = 0 for (let i = 0; i < t.length; i++) { tMap.set(t[i], tMap.has(t[i]) ? tMap.get(t[i]) + 1 : 1) } let match = 0 while (r < s.length) { let c1 = s[r] if (tMap.has(c1)) { window.set(c1, window.has(c1) ? window.get(c1) + 1 : 1) if (window.get(c1) === tMap.get(c1)) { match++ } } r++ while (match === tMap.size) { if (r - l < min) { start = l min = r - l } let c2 = s[l] if (tMap.has(c2)) { window.set(c2, window.get(c2) - 1) if (window.get(c2) < tMap.get(c2)) { match-- } } l++ } } return min === Number.MAX_SAFE_INTEGER ? '' : s.join('').slice(start, start + min) }
|