溧水区住房和城乡建设厅网站,哪里做网站比较快,做百度网站要多少钱,学什么可以做推广网站题目
76. 最小覆盖子串 - 力扣#xff08;LeetCode#xff09;
假设我们用最简单的滑动窗口思路#xff1a;设置左右指针#xff0c;然后移动右指针扩大窗口#xff0c;直到窗口包含所有 t 中的字符#xff0c;再移动左指针缩小窗口。但是我们会发现一些问题
无法准确…题目
76. 最小覆盖子串 - 力扣LeetCode
假设我们用最简单的滑动窗口思路设置左右指针然后移动右指针扩大窗口直到窗口包含所有 t 中的字符再移动左指针缩小窗口。但是我们会发现一些问题
无法准确判断窗口包含了t的所有字符
例如如果tABC窗口ABCB虽然包含ABC但我们不能只检查字符是否存在。
重复字符的处理
例如如果tAAB窗口AAC虽然包含A和A但缺少B。
我们需要增加条件不仅关注字符是否出现还要关注出现的次数使用哈希表记录t中每个字符需要的次数
完整思路
1. 预处理阶段
创建两个哈希表need 记录目标字符串 t 中每个字符需要的数量window 记录当前窗口中每个字符的数量。
遍历字符串 t统计每个字符出现的次数存入 need 哈希表。
初始化左右指针 left 和 right 为 0表示窗口的边界。
初始化 valid 变量为 0用于记录当前窗口中满足条件的字符种类数。
初始化结果相关变量start 为子串起始位置len 为子串长度初始化为一个很大的值。
2. 扩展窗口阶段
移动右指针将字符纳入窗口。
如果当前字符是目标字符即在 need 中更新 window 中该字符的计数。
如果该字符在窗口中的数量恰好等于需要的数量则 valid 加 1。
3. 收缩窗口阶段
当 valid 等于 need 中字符种类数时说明窗口已包含 t 中所有字符且数量都满足。
尝试收缩窗口移动左指针在保证窗口仍然满足条件的情况下找到最小长度的子串。
每次左指针移动前更新最小子串信息如果当前窗口长度小于已知最小长度。
如果左指针指向的字符在 need 中且在 window 中的数量等于需要的数量则移除后会导致窗口不再满足条件需要将 valid 减 1。
更新 window 中对应字符的计数。
4. 重复循环
重复步骤 2 和 3直到右指针到达字符串 s 的末尾。
5. 结果处理
如果找到了满足条件的子串返回该子串否则返回空字符串。
注意处理边界情况如 t 为空字符串s 为空字符串等。
时间复杂度分析
时间复杂度O(n)其中 n 是字符串 s 的长度。
空间复杂度O(k)其中 k 是字符集大小最坏情况下为 O(|\Sigma|)|\Sigma| 是字符集大小。
过程
以例子 s ADOBECODEBANC, t ABC 进行说明。
初始化
need {A:1, B:1, C:1} (t中每个字符需要的数量)
window {} (当前窗口中每个字符的数量)
left 0, right 0 (窗口的左右边界)
valid 0 (已满足条件的字符数)
start 0, len INT_MAX (最小子串的起始位置和长度)
滑动窗口过程
扩展窗口阶段
右指针移动到0: s[0] A
加入窗口: window {A:1}
A在need中且数量满足: valid 1
窗口: [A]valid 1不满足条件
右指针移动到1: s[1] D
加入窗口: window {A:1, D:1}
D不在need中: valid不变
窗口: [AD]valid 1不满足条件
右指针移动到2: s[2] O
加入窗口: window {A:1, D:1, O:1}
O不在need中: valid不变
窗口: [ADO]valid 1不满足条件
右指针移动到3: s[3] B
加入窗口: window {A:1, D:1, O:1, B:1}
B在need中且数量满足: valid 2
窗口: [ADOB]valid 2不满足条件
右指针移动到4: s[4] E
加入窗口: window {A:1, D:1, O:1, B:1, E:1}
E不在need中: valid不变
窗口: [ADOBE]valid 2不满足条件
右指针移动到5: s[5] C
加入窗口: window {A:1, D:1, O:1, B:1, E:1, C:1}
C在need中且数量满足: valid 3
窗口: [ADOBEC]valid 3满足条件
收缩窗口阶段
满足条件开始收缩更新最小值: len 6, start 0
左指针移动到1: s[0] A移出窗口
更新窗口: window {A:0, D:1, O:1, B:1, E:1, C:1}
A在need中且移除后不满足: valid 2
窗口: [DOBEC]valid 2不满足条件停止收缩
继续扩展窗口
右指针移动到6: s[6] O
加入窗口: window {A:0, D:1, O:2, B:1, E:1, C:1}
O不在need中: valid不变
窗口: [DOBECO]valid 2不满足条件
右指针移动到7: s[7] D
加入窗口: window {A:0, D:2, O:2, B:1, E:1, C:1}
D不在need中: valid不变
窗口: [DOBECOD]valid 2不满足条件
右指针移动到8: s[8] E
加入窗口: window {A:0, D:2, O:2, B:1, E:2, C:1}
E不在need中: valid不变
窗口: [DOBECODE]valid 2不满足条件
右指针移动到9: s[9] B
加入窗口: window {A:0, D:2, O:2, B:2, E:2, C:1}
B在need中但之前已满足: valid不变
窗口: [DOBECODEB]valid 2不满足条件
右指针移动到10: s[10] A
加入窗口: window {A:1, D:2, O:2, B:2, E:2, C:1}
A在need中且数量满足: valid 3
窗口: [DOBECODEBA]valid 3满足条件
再次收缩窗口
满足条件开始收缩
左指针移动到1: s[0] D移出窗口
更新窗口: window {A:1, D:1, O:2, B:2, E:2, C:1}
D不在need中: valid不变
窗口: [OBECODEBA]valid 3仍满足条件
左指针继续移动:
移出O,B,E,C,O,D,E
当移出C时valid变为2不满足条件停止收缩
此时窗口长度为4更新 len 4, start 9
窗口: [BANC]valid 3满足条件
最终结果
最小覆盖子串: s.substr(start, len) BANC 为啥最后返回的是s.substr(start, len); 不是数据已经保存在窗口中了嘛 直接返回窗口中的数据不就好了 原因如下
window 哈希表不保存完整字符串
window 哈希表只记录了各个字符及其出现的次数例如 {a: 2, b: 1}
它不保存字符的顺序或完整的子串
窗口可能包含非必要字符
最小窗口可能包含一些不在字符串 t 中的字符
这些字符在 window 中可能有记录但不是所有 window 中的字符都需要
需要保持原始顺序
子串必须保持原始字符串 s 中的字符顺序
从哈希表重建字符串会丢失顺序信息
例如对于输入 s ADOBECODEBANC, t ABC
最小窗口是 BANC
window 哈希表可能包含 {B:1, A:1, N:1, C:1}
但从这个哈希表无法重建 BANC因为我们不知道字符的顺序
因此正确的做法是记录最小窗口的起始位置 start 和长度 len然后使用 s.substr(start, len) 从原字符串中截取出这个子串。这样可以保证返回的是原始顺序的完整子串。
读者可能出现的错误写法
class Solution {
public:string minWindow(string s, string t) {unordered_mapchar,int need;for(char e : t){need[e];}int left 0;int right 0;int len 0;int start 0;int valid 0;unordered_mapchar,int window;while(right s.size()){window[s[right]];if(window[s[right]] need[s[right]]){valid;}right;while(valid need.size()){start left;len min(len,right-left);window[s[left]]--;if(window[s[left]] need[s[left]]){valid--;}left;}}return lenINT_MAX ? : s.substr(start,right);}
};
语法错误 if(window[s[right]] need[s[right]])
和 if(window[s[left]] need[s[left]])
当 s[right] 或 s[left] 不在 need 哈希表中时直接访问 need[s[right]] 会创建一个默认值为0的新键。你应该先检查字符是否在 need 中。
初始化错误
len 初始化为 0应该初始化为 INT_MAX因为我们要找最小窗口
使用 min(len, right-left) 时如果 len0永远不会更新
返回值错误
返回语句中用的是 s.substr(start, right)第二个参数应该是长度 len而不是 right
条件检查不足
需要先检查字符是否在 need 中再进行比较
正确解法
class Solution {
public:string minWindow(string s, string t) {unordered_mapchar,int need;for(char e : t){need[e];}int left 0;int right 0;int len INT_MAX;int start 0;int valid 0;unordered_mapchar,int window;while(right s.size()){char r s[right];right;if(need.count(r)){window[r];if(window[r] need[r]){valid;}}while(valid need.size()){if(len right-left){start left;len right-left;}char l s[left];left;if(need.count(l)){if(window[l] need[l]){valid--;}window[l]--;}}}return lenINT_MAX ? : s.substr(start,len);}
};
