难度：Hard
标签：哈希表；滑动窗口；字符串
链接： https://leetcode.cn/problems/minimum-window-substring/description/
比较容易想到要用滑动窗口来解决，使用两个哈希表来记录信息：cnt_t用于记录字符串t中每个字符出现过的次数，cnt_s用于滑动窗口中的字符的出现次数。
滑动窗口的区间为[left, right]，并记录最小的左右区间（这里我使用一个res数组）。移动right有区间，直到移动到s字符串结束部分。将s[right]加入cnt_s中，如果cnt_s包含cnt_t，则：
- 若当前区间长度小于记录的最小区间长度，更新这个最小区间长度；
- 将cnt_s中
s[left]出现的次数-1；
- left右移+1；
- 重复上面3步，直到cnt_s不包含cnt_t；
最后，若res[0] < 0（最小左区间），说明s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" ；反之，返回最小左右区间中的字符串。
这里的“cnt_s包含cnt_t”是什么意思呢？cnt_t中有的字符cnt_s中都要有，并且cnt_t中字符的次数要小于等于cnt_s中字符出现的次数。
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
| class Solution {
public:
string minWindow(string s, string t) {
unordered_map<char, int> cnt_s, cnt_t;
for (char c : t) {
cnt_t[c]++;
}
int left = 0, right = 0, n = s.length();
int res[2]{-1, n};
while (right < n) {
cnt_s[s[right]]++;
while (cover(cnt_s, cnt_t)) {
if (right - left < res[1] - res[0]) {
res[0] = left;
res[1] = right;
}
cnt_s[s[left++]]--;
}
right++;
}
return res[0] < 0 ? "" : s.substr(res[0], res[1] - res[0] + 1);
}
bool cover(unordered_map<char, int>& cnt_s, unordered_map<char, int>& cnt_t) {
for (auto& [k, v] : cnt_t) {
if (cnt_s.find(k) == cnt_t.end() || cnt_s[k] < v) {
return false;
}
}
return true;
}
};
|