力扣 最小覆盖子串
最小覆盖子串
https://leetcode.cn/problems/minimum-window-substring/
题目描述
题目分析f
覆盖子串：首先根据题意，要求目标字符串的元素必须都在子串中出现过，这表明可以是乱序出现。所以在解决问题是我们需要对子串和目标字符串做匹配，查看子串是否符合要求。
∀ s ∈ S t s . t . s ∈ A n s \begin{align} \forall &s \in \boldsymbol{S_t} \\s.t. \qquad &s \in \boldsymbol{Ans}\end{align} ∀s.t.s∈Sts∈Ans
比较朴素的思路：采用遍历的方法查看是否任意 s ∈ S t s \in \boldsymbol{S_t} s∈St都在 A n s \boldsymbol{Ans} Ans中
更好的方法：通过某种表示手段表示子串和目标字符串从而判断 A n s \boldsymbol{Ans} Ans是否覆盖 S t \boldsymbol{S_t} St（表示方法判断的复杂度应是 O ( 1 ) O(1) 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 ) C_u(S_t) Cu(St)
通过种类，个数的方法表示是否覆盖
实际上通过种类数和个数表示了 S t S_t St，通过维护cntwind、covered_num判断窗口是否覆盖了 S t S_t St
融合了哈希和动归的思想
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;