首页 > 代码库 > LeetCode: Minimum Window Substring [076]
LeetCode: Minimum Window Substring [076]
【题目】
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
For example,
S = "ADOBECODEBANC"
T = "ABC"
Minimum window is "BANC"
.
Note:
If there is no such window in S that covers all characters in T, return the emtpy string ""
.
If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
【题意】
给定一个字符串S和字符串T,找S中找一个最小的窗口,使得这个窗口内包含T中所有的字符。如果找到,则返回最小的窗口子串,如果找不到就返回""。
题目保证,如果存在最小窗口,那么有且仅有一个。
复杂度要求为O(n)
【思路】
1. 先建一个目标map, 记录T中字符出现的对应次数
2. 维护两个指针p1, p2分别指向窗口的头尾,p2依次向后扫描,并不断更新窗口中目标字符出现的次数,一旦T中的字符全部出现,则确定为一个符合条件的窗口, 此时收缩p1来最小化窗口。
3. 重复步骤2直到p2到达字符串S尾。
下面以题目中所给的例子为例看一下最小窗口搜索的全过程
【代码】
class Solution { public: string minWindow(string S, string T) { int sizeS = S.length(); int sizeT = T.length(); if(sizeS==0 || sizeT==0 || sizeT>sizeS)return ""; //建立目标词典 int targetmap[256]; //数组中的默认值不是0,必须进行初始化 int ansmap[256]; memset(targetmap, 0, sizeof(targetmap)); memset(ansmap, 0, sizeof(ansmap)); for(int i=0; i<sizeT; i++){ targetmap[T[i]]++; ansmap[T[i]]++; } //开始搜索 int minWinStart=0, minWinEnd=INT_MAX; int p1=0, p2=0; while(p2<sizeS){//每次一次都是找一个符合条件的窗口,然后收缩p1, 使当前窗口最小 if(targetmap[S[p2]]>0){ //只关心目标字符 ansmap[S[p2]]--; if(ansmap[S[p2]]>=0)sizeT--; //直到T中的字符出现即可,多出现的我们不管 if(0==sizeT){ // 如果已经命中了所有的字符,则记录下当前窗口 //p1向右移动尽可能大的距离,再移动一步窗口就会被破坏 while(true){ if(targetmap[S[p1]]>0){ if(ansmap[S[p1]]<0)ansmap[S[p1]]++; else break; } p1++; } // 记录当前这个窗口 if(p2-p1<minWinEnd-minWinStart){ minWinStart = p1; minWinEnd = p2; } } } p2++; } if(minWinEnd==INT_MAX)return ""; return S.substr(minWinStart, minWinEnd-minWinStart+1); } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。