沛县微网站开发,nas装wordpress,门户网站建设关键点,沼气服务网站建设管理给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串#xff0c;则返回空字符串 。
注意#xff1a;
对于 t 中重复字符#xff0c;我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。如…给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串则返回空字符串 。
注意
对于 t 中重复字符我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。如果 s 中存在这样的子串我们保证它是唯一的答案。
示例 1
输入s ADOBECODEBANC, t ABC
输出BANC
解释最小覆盖子串 BANC 包含来自字符串 t 的 A、B 和 C。示例 2
输入s a, t a
输出a
解释整个字符串 s 是最小覆盖子串。示例 3:
输入: s a, t aa
输出:
解释: t 中两个字符 a 均应包含在 s 的子串中
因此没有符合条件的子字符串返回空字符串。提示
m s.lengthn t.length1 m, n 105s 和 t 由英文字母组成
此题考虑用滑动窗口来做套用模板就成~
string minWindow(string s, string t) {unordered_mapchar,int window,need;//定义哈希表存放窗口中的字符串和t中每个字符的个数for(char c:t) need[c];int left0,right0,val0,lenINT_MAX,stat0;while(rights.size()){char cs[right];right;// 扩大窗口操作if(need.count(c)){//判断right是否在need当中window[c];//如果在就把窗口中该字符1if(window[c]need[c]){//判断窗口中的目标字符个数是否和need中的字符个数相等val;}}while(valneed.size()){// 更新窗口最小长度if(right-leftlen){statleft;lenright-left;}// 缩小窗口操作char ds[left];left;if(need.count(d)){if(window[d]need[d]){val--;}window[d]--;}}}return lenINT_MAX?:s.substr(stat,len);}
提交通过~
