上海网站排名seo公司哪家好,以公开的文化,软件培训机构有哪些?哪个比较好,中信建设有限责任公司 联系方式题目
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串#xff0c;则返回空字符串 “” 。
示例 #xff1a; 输入#xff1a;s “ADOBECODEBANC”, t “ABC” 输出#xff1a;“BANC” 解释#xff1a;…题目
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串则返回空字符串 “” 。
示例 输入s “ADOBECODEBANC”, t “ABC” 输出“BANC” 解释最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、‘B’ 和 ‘C’。
方法
滑动窗口
代码
class Solution {
public:bool check(mapchar, int maps){for(auto it : maps){if(it.second 0){return false;}}return true;}string minWindow(string s, string t) {int n s.size();int n1 t.size();mapchar, int maps;for(int i 0; i n1; i){maps[t[i]];}int pl 0, pr 0;int pl_ret 0;int ret n;bool flag false;while(pr n){if(!check(maps)){if(maps.find(s[pr]) ! maps.end())maps[s[pr]]--;pr;}else{if(pr-pl ret){flag true;ret pr-pl;pl_ret pl;}if(maps.find(s[pl]) ! maps.end())maps[s[pl]];pl;}}if(flag)return s.substr(pl_ret, ret);elsereturn ;}
};
