政务网站无障碍建设网站建设推广 公司

最小覆盖子串

https://leetcode.cn/problems/minimum-window-substring/

题目描述

题目分析f

覆盖子串：首先根据题意，要求目标字符串的元素必须都在子串中出现过，这表明可以是乱序出现。所以在解决问题是我们需要对子串和目标字符串做匹配，查看子串是否符合要求。
$$\begin{array}{rl}\forall & s\in {\mathbf{S}}_{\mathbf{t}}\\ s.t.& s\in \mathbf{Ans}\end{array}$$
比较朴素的思路：采用遍历的方法查看是否任意$s\in {\mathbf{S}}_{\mathbf{t}}$都在$\mathbf{Ans}$中
更好的方法：通过某种表示手段表示子串和目标字符串从而判断$\mathbf{Ans}$是否覆盖${\mathbf{S}}_{\mathbf{t}}$（表示方法判断的复杂度应是$O(1)$）

题目解决

根据题目提示，确定使用滑动窗口的办法。两个注意点，窗口扩大和窗口缩小
当窗口扩大时注意是否满足条件，当满足条件时尝试缩小窗口。注意每当满足条件时，更新最优窗口大小。

遍历覆盖比较法

当满足覆盖时，缩小窗口，一个个判断
代码

class Solution {
public:bool is_covered(int cnt_s[], int cnt_t[]) {for (int i = 'A'; i <= 'Z'; i++) {if (cnt_s[i] < cnt_t[i]) {return false;}}for (int i = 'a'; i <= 'z'; i++) {if (cnt_s[i] < cnt_t[i]) {return false;}}return true;}string minWindow(string s, string t) {int slen = s.size(), tlen = t.size();string ans;if(slen < tlen) return ans;int ansleft = -1, ansright = slen;int cntwind[128] = {0}, cntt[128]={0};for(char &c : t){++cntt[c];}int left = 0;for(int right = 0; right < slen; ++right){++cntwind[s[right]];while(is_covered(cntwind, cntt)){if(right - left < ansright - ansleft){ansleft = left;ansright = right;}--cntwind[s[left]];++left;}   }return ansleft < 0 ? "" : s.substr(ansleft, ansright - ansleft + 1);}
};

表示覆盖比较法

通过预先设定窗口表示——$C_u(S_t)$
通过种类，个数的方法表示是否覆盖
实际上通过种类数和个数表示了$S_t$，通过维护cntwind、covered_num判断窗口是否覆盖了$S_t$
融合了哈希和动归的思想

class Solution {
public:string minWindow(string s, string t) {int slen = s.size(), tlen = t.size();string ans;if(slen < tlen) return ans;int ansleft = -1, ansright = slen;int cntwind[128] = {0};int covered_num = 0;for(char &c : t){if(cntwind[c] == 0){++covered_num;}--cntwind[c];}int left = 0;for(int right = 0; right < slen; ++right){++cntwind[s[right]];if(cntwind[s[right]] == 0) --covered_num;while(covered_num == 0){if(right - left < ansright - ansleft){ansleft = left;ansright = right;}--cntwind[s[left]];if(cntwind[s[left]] < 0) ++covered_num;++left;}   }return ansleft < 0 ? "" : s.substr(ansleft, ansright - ansleft + 1);}
};

总结，巧妙的通过数字的变化表示了窗口状态的变化
++cntwind[s[right]]; if(cntwind[s[right]] == 0) --covered_num;