建行官方网站首页,扁平式风格网站,买了一个域名怎么做网站,专业网站优化公司排名题目链接#xff1a;leetcode 76
1.题目
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串#xff0c;则返回空字符串 “” 。
注意#xff1a; 对于 t 中重复字符#xff0c;我们寻找的子字符串中该字符数…题目链接leetcode 76
1.题目
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串则返回空字符串 “” 。
注意 对于 t 中重复字符我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 如果 s 中存在这样的子串我们保证它是唯一的答案。
2.示例
1示例 1 输入s “ADOBECODEBANC”, t “ABC” 输出“BANC” 解释最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、‘B’ 和 ‘C’。
2示例 2 输入s “a”, t “a” 输出“a” 解释整个字符串 s 是最小覆盖子串。
3示例 3: 输入: s “a”, t “aa” 输出: “” 解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中 因此没有符合条件的子字符串返回空字符串。
4提示 m s.length n t.length 1 m, n 10^5 s 和 t 由英文字母组成
3.分析
以i和j为s的两个端点对于一个i我们首先依次向右移动j直到满足[i,j]符合涵盖t的关系再将i移动到第一个t包含的字母处依次更新维护子串中包含字母的次数即可复杂度为O(mn)
4.代码
class Solution {
public:int st10,ed10;int i-1,j0;bool flagfalse;vectorchar V;mapchar,int map1,map2;bool check(){for(int k0;kV.size();k)if(map1[V[k]]map2[V[k]]) return false;return true;}string minWindow(string s, string t) {int ns.size(),ansn1;for(int k0;kt.size();k){if(map1.count(t[k])0) {map1[t[k]]1;V.push_back(t[k]);}else map1[t[k]];map2[t[k]]0;}for(int k0;kn;k) map2[s[k]];if(check()false) return ;for(int k0;kn;k) map2[s[k]]0;map2[s[0]]1;while(injn){if(i0map2.count(s[i])!0)map2[s[i]]--;i;while(check()falsej1n) {j;map2[s[j]];}while(map1.count(s[i])0i1j) {map2[s[i]]--;i;}if(check()){if(j-i1ans){ansmin(ans,j-i1);st1i;ed1j;}}}return s.substr(st1,ans);}
};
