恩施北京网站建设,c 网站开发入门视频教程,上行10m企业光纤做网站,网站自适应手机76. 最小覆盖子串s
初始化和特判
//本题做题思想
//从头开始#xff0c;首先找到一个包含所有字母的字串#xff0c;将i移动到包含字串字母的位置#xff0c;然后更新长度和字符串ans后#xff0c;
//i的位置加1#xff0c;j的位置也加1#xff0c;从新开始上面的流程首先找到一个包含所有字母的字串将i移动到包含字串字母的位置然后更新长度和字符串ans后
//i的位置加1j的位置也加1从新开始上面的流程找一个包含所有字符串t字母的子串unordered_mapchar,intneed;//need记录下来每个字母‘需要’多少为正数//对于不需要的字母和本来需要但超出数量的字母依旧记录但减1后变负数int cnt 0;//cnt记录总共需要多少个int ansnum 100010;//ans记录最短的字符子串ansnum维护最小的长度string ans ;if(s.size() t.size() ) return ans;if(s t) return s;统计字符数
for(int i 0; i t.size();i){need[t[i]];
}
cnt t.size();找满足题目条件的字符子串
int i 0, j 0;while(i s.size()){while(j s.size() cnt 0){if(need[s[j]] 0) cnt--;need[s[j]]--;if(cnt 0 || j s.size() - 1)break;j;//while循环记得递增}if(cnt ! 0) return ans;while(i j){if(need[s[i]] 0) break;need[s[i]];i;//while循环记得递增}if(j - i 1 ansnum){ans s.substr(i, j - i 1);ansnum j - i 1;}cnt 1;need[s[i]];i,j;//记得递增}具体解析过程可看此题解本题解为C实现链接题解为python
