题目
给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。
示例：
输入: S = &“;ADOBECODEBANC&”;, T = "ABC" 输出: "BANC"
说明：
- 如果 S 中不存这样的子串，则返回空字符串
""。 - 如果 S 中存在这样的子串，我们保证它是唯一的答案。
给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。
示例：
输入: S = "ADOBECODEBANC", T = "ABC" 输出: "BANC"
说明：
- 如果 S 中不存这样的子串，则返回空字符串
""。 - 如果 S 中存在这样的子串，我们保证它是唯一的答案。
思路
还是滑动窗口，与438. 找到字符串中所有字母异位词类似的思路。
不同的地方在于，维护窗口的策略
这个题目是维护 窗口内部的符合Ｔ字符的长度 等于 Ｔ的长度
４３８那个题目是维护 窗口长度 等于 Ｔ的长度
代码
class Solution {
public:
string minWindow(string s, string t) {
int ans = s.size(), cnt[128] = {
0};
string res;
for (char c : t) ++cnt[c];
for (int l = 0, r = 0, len = 0; r < s.size(); r++) {
if (--cnt[s[r]] >= 0) ++len;
while (len == t.size()) {
if (r - l + 1 <= ans) {
ans = r - l + 1;
res = s.substr(l, r - l + 1);
}
if (++cnt[s[l++]] > 0) --len;
}
}
return res;
}
};
执行用时 : 12 ms, 在所有 C++ 提交中击败了 96.65% 的用户
总结
滑动窗口
- 滑入滑出的操作互逆
- 根据题意如何维护一个窗口的意义。
京公网安备 11010502036488号