[LeetCode]76.Minimum Window Substring

题目

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.

分析

详细些参考：[算法系列之二十二]包含T全部元素的最小子窗口

代码

/*--------------------------------------------
*   日期：2015-02-24
*   作者：SJF0115
*   题目: 76.Minimum Window Substring
*   网址：https://oj.leetcode.com/problems/minimum-window-substring/
*   结果：AC
*   来源：LeetCode
*   总结：
------------------------------------------------*/
#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;


class Solution {
public:
    string minWindow(string S, string T) {
        int slen = S.size();
        int tlen = T.size();
        if(slen <= 0 || tlen <= 0){
            return "";
        }//if
        int minWinStart = 0,minWinEnd = 0;
        int minWinLen = INT_MAX;
        // 存储到目前为止遇到过的T中字符总数
        int count = 0;
        // 存储T中不同字符的总数
        int needFind[256] = {0};
        for(int i = 0;i < tlen;++i){
            ++needFind[T[i]];
        }//for
        // 存储到目前为止遇到过的不同字符的总数
        int hasFound[256] = {0};
        int val;
        for(int start = 0,end = 0;end < slen;++end){
            val = S[end];
            // 跳过不在T中的字符
            if(needFind[val] == 0){
                continue;
            }//if
            ++hasFound[val];
            if(hasFound[val] <= needFind[val]){
                ++count;
            }//if
            // 找到一个有效窗口
            if(count == tlen){
                int startVal = S[start];
                while(needFind[startVal] == 0 ||
                      hasFound[startVal] > needFind[startVal]){
                    if(hasFound[startVal] > needFind[startVal]){
                        --hasFound[startVal];
                    }//if
                    ++start;
                    startVal = S[start];
                }//while
                // 更新最小窗口
                int curWinLen = end - start + 1;
                if(curWinLen < minWinLen){
                    minWinLen = curWinLen;
                    minWinStart = start;
                    minWinEnd = end;
                }//if
            }//if
        }//for
        if(count != tlen){
            return "";
        }//if
        return S.substr(minWinStart,minWinEnd - minWinStart + 1);
    }
};

int main() {
    Solution solution;
    string S("acbbaca");
    string T("aba");
    cout<<solution.minWindow(S,T)<<endl;
}

运行时间

相似题目：

[经典面试题][搜狗]在一个字符串中寻找包含全部出现字符的最小字串

<script type="text/javascript"> $(function () { $('pre.prettyprint code').each(function () { var lines = $(this).text().split('\n').length; var $numbering = $('<ul/>').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('<li/>').text(i)); }; $numbering.fadeIn(1700); }); }); </script>