江苏龙网

  1. 首页 > 人文 > >

碰碰战队|C++11题解系列-075 最小覆盖子串，leetcode


题目给你一个字符串S、一个字符串T 。 请你设计一种算法 ， 可以在O(n)的时间复杂度内 ， 从字符串S里面找出：包含T所有字符的最小子串 。 示例：输入：S="ADOBECODEBANC",T="ABC"输出："BANC"提示：如果S中不存这样的子串 ， 则返回空字符串"" 。 如果S中存在这样的子串 ， 我们保证它是唯一的答案 。 解题代码与测试////Createdbytannzhon2020/8/9.///**最小覆盖子串给你一个字符串S、一个字符串T 。 请你设计一种算法 ， 可以在O(n)的时间复杂度内 ， 从字符串S里面找出：包含T所有字符的最小子串 。 示例：输入：S="ADOBECODEBANC",T="ABC"输出："BANC"提示：如果S中不存这样的子串 ， 则返回空字符串"" 。 如果S中存在这样的子串 ， 我们保证它是唯一的答案 。 */#include#include#includeusingstd::string;classSolution{public:stringminWindow(strings,stringt){stringres="";std::unordered_mapletterCnt;intleft=0,cnt=0,minLen=INT_MAX;for(charc:t)++letterCnt[c];for(inti=0;i<s.size();++i){if(--letterCnt[s[i]]>=0)++cnt;while(cnt==t.size()){if(minLen>i-left+1){minLen=i-left+1;res=s.substr(left,minLen);}if(++letterCnt[s[left]]>0)--cnt;++left;}}returnres;}};intmain(intargc,char**argv){Solutions;std::stringS="ADOBECODEBANC",T="ABC";std::cout<<s.minWindow(S,T)<<std::endl;return0;}解题思路分析这道题给了我们一个原字符串S ， 还有一个目标字符串T ， 让在S中找到一个最短的子串 ， 使得其包含了T中的所有的字母 ， 并且限制了时间复杂度为O(n) 。 这道题的要求是要在O(n)的时间度里实现找到这个最小窗口字串 ， 暴力搜索BruteForce肯定是不能用的 ， 因为遍历所有的子串的时间复杂度是平方级的 。 那么来想一下 ， 时间复杂度卡的这么严 ， 说明必须在一次遍历中完成任务 ， 当然遍历若干次也是O(n) ， 但不一定有这个必要 ， 尝试就一次遍历拿下！那么再来想 ， 既然要包含T中所有的字母 ， 那么对于T中的每个字母 ， 肯定要快速查找是否在子串中 ， 既然总时间都卡在了O(n) ， 肯定不想在这里还浪费时间 ， 就用空间换时间（也就算法题中可以这么干了 ， 七老八十的富翁就算用大别墅也换不来时间啊 。
依依东望 ， 望的就是时间呐T.T） ， 使用HashMap ， 建立T中每个字母与其出现次数之间的映射 ， 那么你可能会有疑问 ， 为啥不用HashSet呢 ， 别急 ， 讲到后面你就知道用HashMap有多妙 ， 简直妙不可言～目前在脑子一片浆糊的情况下 ， 我们还是从简单的例子来分析吧 ， 题目例子中的S有点长 ， 换个短的S="ADBANC" ， T="ABC" ， 那么肉眼遍历一遍S呗 ， 首先第一个是A ， 嗯很好 ， T中有 ， 第二个是D ， T中没有 ， 不理它 ， 第三个是B ， 嗯很好 ， T中有 ， 第四个又是A ， 多了一个 ， 礼多人不怪嘛 ， 收下啦 ， 第五个是N ， 一边凉快去 ， 第六个终于是C了 ， 那么貌似好像需要整个S串 ， 其实不然 ， 注意之前有多一个A ， 就算去掉第一个A ， 也没事 ， 因为第四个A可以代替之 ， 第二个D也可以去掉 ， 因为不在T串中 ， 第三个B就不能再去掉了 ， 不然就没有B了 。 所以最终的答案就"BANC"了 。 通过上面的描述 ， 你有没有发现一个有趣的现象 ， 先扩展 ， 再收缩 ， 就好像一个窗口一样 ， 先扩大右边界 ， 然后再收缩左边界 ， 上面的例子中右边界无法扩大了后才开始收缩左边界 ， 实际上对于复杂的例子 ， 有可能是扩大右边界 ， 然后缩小一下左边界 ， 然后再扩大右边界等等 。 这就很像一个不停滑动的窗口了 ， 这就是大名鼎鼎的滑动窗口SlidingWindow了 ， 简直是神器啊 ， 能解很多子串 ， 子数组 ， 子序列等等的问题 ， 是必须要熟练掌握的啊！


推荐阅读


上一篇：科技生活大侠|华为将成最大赢家，如用户被迫在iPhone与微信之间二选一

下一篇：产业气象站|中芯国际第二季度营收大增！，不断提升！华为麒麟710A立功