题目描述
给定两个字符串:S 和 T,请找到 S 中最短的一段,包含 T 中所有字符。
注意:
- 如果 S 中不存在这样的方案,则返回
""
; - 如果 S 中存在这样的方案,则数据保证答案一定唯一;
样例
输入:S = "ADOBECODEBANC", T = "ABC"
输出:"BANC"
算法
(滑动窗口) O(n)
首先用哈希表统计出 T 中所有字符出现的次数,哈希表可以用C++中的 unordered_map
,不了解用法的同学可以点这里。
然后我们用两个指针 i,j(i≥j)来扫描整个字符串,同时用一个哈希表统计 i,j 之间每种字符出现的次数,每次遍历需要的操作如下:
- 加入 s[i],同时更新哈希表;
- 检查 s[j] 是否多余,如果是,则移除 s[j];
- 检查当前窗口是否已经满足 T 中所有字符,如果是,则更新答案;
时间复杂度分析:两个指针都严格递增,最多移动 n 次,所以总时间复杂度是 O(n)。
C++ 代码
class Solution {
public:
string minWindow(string s, string t) {
unordered_map<char, int> hash;
int cnt = 0;
for (auto c : t)
{
if (!hash[c]) cnt ++ ;
hash[c] ++ ;
}
string res = "";
for (int i = 0, j = 0, c = 0; i < s.size(); i ++ )
{
if (hash[s[i]] == 1) c ++ ;
hash[s[i]] -- ;
while (c == cnt && hash[s[j]] < 0) hash[s[j ++ ]] ++ ;
if (c == cnt)
{
if (res.empty() || res.size() > i - j + 1) res = s.substr(j, i - j + 1);
}
}
return res;
}
};
贴一个
注释版
代码,详情剖析版
可以看这里啦 详细题解:// 双指针 滑动窗口 要满足单调性。即 i, j 指针 均只能 朝着 一个方向移动, 不能朝一个方向移动 再 向另一个方向移动. // 设滑动窗口 s[j ~ i], 设 指针 i 为 滑动窗口的 终点, 指针 j 为 滑动窗口的 起点. // 设 哈希表 hw(hash_window) 存的是 滑动窗口内 各字符的数量, ht存的是 字符串t内各字符数量. // // 问题 1 :如何 快速判断 滑动窗口 s[j ~ i] 内 是否 已经包含了 t内所有字符了呢(每种字符可能重复)? // 滑动窗口 内的 有效字符 总数量 cnt = t.size(), 就说明已经包含了 t 内所有字符. // 问题 2 :那么 什么是 有效字符呢? // 如果 此时 新加入了 s[i]字符之后, hw[s[i]] <= ht[s[i]], 此时的字符 s[i]有用, 就算有效字符, cnt ++. // 如果 新加入了 s[i]字符之后, 有 hw[s[i]] > ht[s[i]] 了, 说明加入当前字符s[i] 之前, 滑动窗口内 s[i]的数量 // --- 就已经 达到了 t内这个字符s[i]的数量, 原本关于 字符s[i] 就已经达标, 现在再加就是冗余, 就是无效字符. // // 问题 3 :滑动窗口 s[j ~ i]的 起点 指针 j 什么时候 才 向右 移动? // 如果 s[j]处的字符 (字符记为#) 的数量 大于 t 中 这个字符 # 的数量, 即 hw[s[j]] > ht[s[j]], // --- j 就可以向右移动, 因为 s[j] 处的字符 # 的数量 冗余了, j 向右移动的时候, 同时 将 hw[s[j]] -- // 问题 4 : 有效字符的数量 cnt 变化是靠的什么呢? // cnt ++ 只能通过 指针 i 向右移动, 但是 注意 指针 i 不一定 每次 向右移动 都会 使有效字符 cnt ++。 // 指针 j 向右移动 不会影响 有效字符cnt 的数量, 即 虽然不会 cnt ++, 但是也不会出现 导致cnt --. // // 问题 5 : 指针 i 和 指针 j 的作用, 这里 打个 形象的比喻 ~~~ // 指针 i 的作用是 开源,负责 增加有效字符cnt 的数量, 开疆破土, 助力 有效字符数量 cnt 早日达到 t.size(); // 指针 j 的作用是 节流,负责 将 指针 i 开辟的疆土 中 无价值 的部分 即 冗余的字符 回收,达到 最小 覆盖子串的目的。 // // 问题 6 :双指针工作的流程 是 怎样的呢? 明白了 指针 j 和 i 的作用 就很好理解啦 ~ // (1) 肯定是 指针 i 先移动, hw[s[i]] ++, 然后看看 是否 会 增加 cnt, 通过 if (hw[s[i]] <= ht[s[i]]) 来判断 // (2) i 每次向右移动一步之后, 每次 i 移动之后 都可能会导致 cnt == t.size(), 因为题目是求 最小 覆盖子串, 所以 // --- 在 判断 if (cnt == t.size()) 之前 要 先 用 j 将 无用的 字符回收, 达到 最小覆盖子串 的目的 // --- j 就负责 看看 i 之前开辟的疆土里面有没有 冗余的字符, 有的话就回收, hw[s[j]] -- 同时 j ++ // --- 注意 j 回收的时候, 可能会一次回收多个, 所以用的是 while 而不是 if.(比如 s="baaabc", t="bc") // (3) i 每次开辟完新的疆土 同时 j 也回收了 可能存在的 无价值的 冗余字符, 就可以判断 cnt == t.size()啦 ~~ class Solution { public: string minWindow(string s, string t) { // hw 存的是 滑动窗口内 各字符数量, ht 存的是 字符串t 的 各字符数量 unordered_map<char, int> hw, ht; // 也可开一个哈希表作差,但是开两个思路更清晰 for (auto c: t) ht[c] ++ ; // 统计 字符串 t 中 各字符 数量 string res; int cnt = 0; // 注意: cnt 中 存的是 有效字符的数量 for (int i = 0, j = 0; i < s.size(); i ++ ) { // (1) 指针 i 先移动, hw[s[i]] ++, 然后看看 是否 会 增加 cnt, 通过 if (hw[s[i]] <= ht[s[i]]) 来判断 hw[s[i]] ++ ; if (hw[s[i]] <= ht[s[i]]) cnt ++ ; // (2) j 就负责 看看 i 之前开辟的疆土里面有没有 冗余的字符, 有的话就回收, hw[s[j]] -- 同时 j ++ // 每次 i 移动完 之后, 判断 j 能不能向右移动, 注意 j 可以连续移动, 用while 不是 if // while (hw[s[j]] > ht[s[j]]) hw[s[j ++ ]] -- ; // 是 while, 不是 if while (j <= i && hw[s[j]] > ht[s[j]]) hw[s[j ++ ]] -- ; // 加上 j <= i,防止字符串下标越界 // (3) i 每次开辟完新的疆土 同时 j 也回收了 可能存在的 无价值的 冗余字符, 就可以判断 cnt == t.size()啦 if (cnt == t.size()) { // 更新答案 if (res.empty() || i - j + 1 < res.size()) // 注意 res.empty() res = s.substr(j, i - j + 1); } } return res; } };
棒!
哈哈哈哈哈哈 太妙了!!
我夸我自己?
yxchb!
膜拜这个cnt 的思路 滑动窗口好写 自己开了两个哈希表来维护条件满足 用了y总思路快了一倍多
加油hh
while (c == cnt && hash[s[j]] < 0) hash[s[j ++ ]] ++ ;
这句代码中,
j ++
的意思是删除当前j
指向的这个字符对吗?但是我不理解
hash[s[j]] ++
这里是做什么?窗口中的所有字符,每出现一次,就在哈希表中减一,所以当从窗口中删除一个字符的时候,就加1。
j ++
表示将j
从窗口中删除。from collections import defaultdict class Solution: def minWindow(self, s: str, t: str) -> str: hash = defaultdict(lambda: 0) # 默认值为0,哈希表存的是窗口中每个字母还缺多少没被覆盖 for i in t: hash[i] += 1 cnt = len(hash) res = '' i = 0; j = 0; c = 0 while j < len(s): if hash[s[j]] == 1: c += 1 hash[s[j]] -= 1 # while c == cnt and hash[s[i]] < 0: # hash[s[i]] += 1 # i += 1 # 当缺的个数是负数时,说明这个字母无关紧要,如果缺的个数为0,删完之后就会缺一个,此时就停 while hash[s[i]] < 0: hash[s[i]] += 1 i += 1 if i == len(s): break # 注意当 c<cnt时左指针是不能右移的? if c == cnt and not len(res) or len(res) > j - i + 1: res = s[i: j + 1] j += 1 return res
python如果没有c==cnt的话左指针可能会越过s字符串边界,需要要判断一下,那为何C++里面就可以通过呢
按道理应该加一下
c == cnt
的判断。不过程序运行过程中如果发生数组越界,是不一定会报错的,运行结果会比较随机。因为大多数C++实现里,std::string会在尾部添加一个’\0’,所以越界的时候就变成hash[‘\0’]了,但正如y总所说没有报错
看录播里的代码 是while ( hash[s[j]] < 0) hash[s[j ]] ;这个里面没有c==cnt,但是今天跑了一遍,报错越界了
这里应该加上
c == cnt
,否则j
可能会越界。hash[s[j ++ ]] ++
这样 j 不会越界吗不会滴。
hash[]
中存储的是t
中每个字母出现的次数,减去s[j~i]
中出现的次数,所以当j > i
时,hash[]
中的所有值一定大于等于0,此时循环就会终止。while (c == cnt && hash[s[j]] < 0) hash[s[j ]] ;这一句太厉害了
是的hh 双指针算法的核心啊
请问hash[s[j]] == 0的情况是什么样的?如果s[j]是在t中没有出现的话,那么hash[s[j]]不就是多余的吗?
hash[c]
表示的是当前c
这个字母还缺多少个,hash[s[j]] == 0
表示s[j]
这个字母已经足够了 。如果s[j]
是在t中没有出现的话,hash[s[j]]
可以不用记录,不过记录一下也不影响算法正确性。明白了,也就是说如果一个字母如果没在t中出现的话,会先被–变为-1;那么当hash[s[j]] == 0的时候这个j字母肯定是在t里面出现了的,谢谢y总的解答
嗯嗯不客气
如果加上详细注释就更好啦!