seo sem 做网站,长沙长沙建设网站,国外空间做网站怎么样,佛山微网站开发哪家好最小覆盖子串 https://leetcode.cn/problems/minimum-window-substring/ 题目描述 题目分析f
覆盖子串#xff1a;首先根据题意#xff0c;要求目标字符串的元素必须都在子串中出现过#xff0c;这表明可以是乱序出现。所以在解决问题是我们需要对子串和目标字符串做匹配首先根据题意要求目标字符串的元素必须都在子串中出现过这表明可以是乱序出现。所以在解决问题是我们需要对子串和目标字符串做匹配查看子串是否符合要求。 ∀ 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;
