首页 > 代码库 > Minimum Window Substring
Minimum Window Substring
尾指针不断往后扫,当扫到有一个窗口包含了所有T的字符,头指针收缩头指针。得到窗口最小的情况
class Solution { public: string minWindow(string S, string T) { int slen = S.size(); int tlen = T.size(); // record T[i] int need[256] = {0},has[256] = {0}, cnt = 0, ans = slen+1, mBegin, mEnd ; for(int i = 0; i < tlen; i++) ++need[T[i]]; for(int begin = 0, end = 0; end < slen; end++){ if(need[S[end]] == 0) continue; //find T[i] ++has[S[end]]; if(has[S[end]] <= need[S[end]]) ++cnt; //number of map if(cnt == tlen){ while(need[S[begin]] == 0 || has[S[begin]] > need[S[begin]]){ if(has[S[begin]] > need[S[begin]]) --has[S[begin]]; begin++; } int l = end - begin+1; if(l < ans){ mBegin = begin; mEnd = end; ans = l; } } } return ans <= slen?S.substr(mBegin, mEnd- mBegin+1):""; } };
Minimum Window Substring
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。