[算法系列之二十二]包含T全部元素的最小子窗口

题目描述

给定一个包含一系列字符的集合T和字符串S,请在字符串S中找到一个最小的窗口，这个窗口中必须包含T中的所有字符。
例如,
S = “ADOBECODEBANC”
T = “ABC”

最小窗口是“BANC”

分析

这是一个有趣的问题,这个有趣的问题有多种方法来解决，最好的方法是非常简单，美丽的。
在这篇文章中,我首先说明了一个方法,是我第一次遇见这个问题时想到的。我的第一个方法有点复杂,同时也不是最好的解决方案(时间复杂度为O(NlgM))。在这篇文章的后面中,我介绍一个比较好的方法,时间复杂度为O(N)。
Hint:
使用上面的示例中S =“ADOBECODEBANC”，S =“ABC”,我们可以很容易地找到第一个窗口“ADOBEC”，包含了T中所有元素。另一个可能的候选者是“ADOBECODEB A”。事实上,我们应该跳过这个,因为在这个窗口中存在一个子窗口“CODEBA”，既短又满足约束条件。最后考虑的一个窗口是“BANC”,这也是最小的窗口。

为了有效地解决这个问题,下面我们需要考虑的两个关键点:

我们如何确定一个特定的窗口包含T ?(最理想的情况是O(1)时间)。
我们如何有效的选择所有窗口?(最理想的情况是不包括含有子窗口的那些窗口)。

我们绝对需要哈希表（Hash Table）的帮助。哈希表能在O(1)时间内告诉我们一个字符是否在T 中。

O(N lg M) 方法:

当我第一次遇到这一问题,我想到了另一个表,记录字符上次出现的位置。也就是说,当我第一次看到字符’A‘,我记录它的位置是0。我每次再见到’ A ‘,我就用新位置代替它原先的位置。这种方法虽然很简单,但是缺陷也很明显。请注意,T不包含重复的字符吗?如果T包含了重复的字符,如“AABC”,这种方法就不能使用了。

在这种情况下,补救措施是维持一个队列(而不是表),T中每个不同字符对应一个队列（例如：字符A对应一个队列，字符B对应一个队列。。。）。例如,假设T =“AABC”,当你第一次遇到“A”,把它的所在位置放入“A”队列中(最初是空的)。当你再次遇到“A ”时,把它的位置放入“A”队列末尾。第三次遇到“A”时,弹出第一个元素,并把这次遇到的A所在位置放入“A”队列末尾。通过弹出元素,我们不包括那些包含子窗口的窗口。这种方法很有效,但困难是双重的:

我们没有办法从队列本身直接确定窗口的开始和结束位置。一个最自然的方法是扫描整个队列得到最小值和最大值。我们如何确定这个窗口是否满足约束条件呢?我们不得不扫描整个队列来检查所有队列大小总和是否等于T的长度。

我解决上述问题的方法是维护一个sorted map,它映射到每一个字符。这样我们能在O(1)时间内获取最小值和最大值的位置。但这样做会花费额外的时间。每次你从队列中弹出一个元素,你不得不通过删除相应的元素和插入一个新元素来更新map。检查窗口是否满足约束条件,我们必须查看map的大小,如果map的大小等于T的长度就代表找到一个有效的窗口。

这个方法的时间复杂度是O(N lg M),其中N是S的长度,和M是T的长度。额外的lgM是由于在map中删除和插入一个元素的额外花费，每个最坏情况花费O(lgM)时间。（注意,M是map的最大大小。）

/*---------------------------------------------
*   日期：2015-02-24
*   作者：SJF0115
*   题目: 22.包含T全部元素的最小子窗口
*   来源：算法系列
*   博客：
-----------------------------------------------*/
#include <iostream>
#include <map>
#include <queue>
#include <climits>
#include <algorithm>
using namespace std;

bool MinWindow(string s,string t,int &startWin,int &endWin){
    int slen = s.size();
    int tlen = t.size();
    if(slen <= 0 || tlen <= 0){
        return false;
    }//if
    // 存储T中不同字符的总数
    int needFind[256] = {0};
    for(int i = 0;i < tlen;++i){
        ++needFind[t[i]];
    }//for
    // 不在T中的元素设置为-1
    for(int i = 0; i < 256;++i){
        if(needFind[i] == 0){
            needFind[i] = -1;
        }//if
    }//for
    int minWinLen = INT_MAX;
    // 队列数组，每个不同的字符都对应一个队列
    queue<int> q[256];
    // 第一个元素和最后一个元素表明了窗口的开始和结束位置
    map<int,char> m;
    int val;
    for(int i = 0;i < slen;++i){
        val = s[i];
        // 跳过不在T中的元素
        if(needFind[val] == -1) {
            continue;
        }//id
        // 字符放入队列
        if(q[val].size() < needFind[val]) {
            q[val].push(i);
            m[i] = val;
        }//if
        // 取代队列中的字符，更新map中对应元素
        else{
            int idxToErase = q[val].front();
            map<int,char>::iterator it = m.find(idxToErase);
            m.erase(it);
            m[i] = val;
            q[val].pop();
            q[val].push(i);
        }//else
        if(m.size() == tlen){
            int end = m.rbegin()->first;
            int start = m.begin()->first;
            int winLen = end - start + 1;
            if (winLen < minWinLen) {
                minWinLen = winLen;
                startWin = start;
                endWin = end;
            }//if
        }//if
    }//for
    return (m.size() == tlen);
}

int main() {
    string s("acbbaca");
    string t("aba");
    int start,end;
    bool result = MinWindow(s,t,start,end);
    if(result){
        cout<<s.substr(start,end-start+1)<<endl;
    }//if
    else{
        cout<<"未找到"<<endl;
    }//else
    return 0;
}

O(N)方法：

注意到上面的思路是非常复杂的。它使用了一个哈希表,一个队列还有一个sorted map。在面试过程中,给出的问题往往是比较短的，解决方案通常在50行代码左右。所以你有必要大声说出你在想什么,时刻保持与面试官进行沟通。检查你的方法是否是没有必要的复杂,他/她可以给你指导。最不好的就是就是你被困在一点,什么也不说。

为了阐述这个思路,我使用一个不同上面的例子:S = “acbbaca”,T = “aba”。这个思路主要是遍历S时使用了两个指针begin和end(窗口开始和结束位置)和两个数组(needToFind 和 hasFound)。needToFind存储T中不同字符的总数，hasFound存储到目前为止遇到过的不同字符的总数。我们也使用一个count变量来存储到目前为止遇到过的T中字符总数(当hasFound[x]超过needToFind[x]时不用计数)。当count等于T的长度时,我们就找到了一个有效的窗口。

每次我们向前移动end指针(指向一个元素x),我们会使hasFound[x]加一。如果hasFound[x]是小于或等于needToFind[x]时count加一。为什么?当满足约束条件(即count等于T的大小),在满足约束的条件下，我们开尽可能的向右移动begin指针。

我们如何检查是否满足约束条件呢?假设begin指向一个元素x,我们检查hasFound[x]是否大于needToFind[x]。如果是,我们可以使hasFound[x]减一,在不破坏约束条件的前提下向前移动begin指针。相反,如果不是,我们立即停止向前移动begin指针，以防破坏约束条件。

最后,我们检查最小窗口长度是否小于当前的最小窗口长度。如果不是则更新最小窗口长度。

本质上,该算法找到满足约束的第一个窗口后,仍然继续保持约束条件。

（1） S = “acbbaca” T = “aba“

（2）第一个找到最小的窗口。我们无法向前移动begin指针当hasFound[‘a’]== needToFind[‘a’]= = 2。向前移动意味着打破约束。

（3）第二个窗口。begin指针仍然指向第一个元素“a”。hasFound[’ a ‘]（3）大于needToFind[‘a’]（2）。我们使hasFound[’ a ‘],向右移动begin指针。

（4）我们跳过元素c，因为它不在T中。现在begin指针指向元素b。hasFound[b]（2）大于needToFind[b]（1）。我们使hasFound[b]减一,同时向右移动begin指针。

（5）begin指针现在指向下一个元素b。hasFound[b]（1）等于needToFind[b]（1）。我们立即停止,这是我们新发现的最小的窗口。

begin指针和end指针最坏情况下向前移动至多N步（N 是字符串S的长度），加起来是2N时间，因此时间复杂度是O(N)。

/*---------------------------------------------
*   日期：2015-02-24
*   作者：SJF0115
*   题目: 22.包含T全部元素的最小子窗口
*   来源：算法系列
*   博客：
-----------------------------------------------*/
#include <iostream>
#include <climits>
#include <algorithm>
using namespace std;

// Returns false if no valid window is found. Else returns
// true and updates start and end with the
// starting and ending position of the minimum window.
bool MinWindow(string s,string t,int &startWin,int &endWin){
    int slen = s.size();
    int tlen = t.size();
    if(slen <= 0 || tlen <= 0){
        return false;
    }//if
    // 存储T中不同字符的总数
    int needFind[256] = {0};
    for(int i = 0;i < tlen;++i){
        ++needFind[t[i]];
    }//for
    // 存储到目前为止遇到过的不同字符的总数
    int hasFound[256] = {0};
    // 存储到目前为止遇到过的T中字符总数
    int count = 0;
    int minWin = INT_MAX;
    int endEle;
    for(int start = 0,end = 0;end < slen;++end){
        endEle = s[end];
        // 剪枝 无用字符(T中字符为有用字符)
        if(needFind[endEle] == 0){
            continue;
        }//if
        ++hasFound[endEle];
        if(hasFound[endEle] <= needFind[endEle]){
            ++count;
        }//if
        // 找到一个有效窗口
        if(count == tlen){
            int begEle = s[start];
            // 满足：字符为无用字符，begEle元素找多了 start指针才向右移动
            while(needFind[begEle] == 0 || hasFound[begEle] > needFind[begEle]){
                if(hasFound[begEle] > needFind[begEle]){
                   --hasFound[begEle];
                }//if
                ++start;
                begEle = s[start];
            }//while
            // 更新最小窗口
            int curWin = end - start + 1;
            if(curWin < minWin){
                minWin = curWin;
                startWin = start;
                endWin = end;
            }//if
        }//if
    }//while
    return (count == tlen);
}

int main() {
    string s("ADOBECODEBANC");
    string t("ABC");
    int start,end;
    bool result = MinWindow(s,t,start,end);
    if(result){
        cout<<s.substr(start,end-start+1)<<endl;
    }//if
    else{
        cout<<"未找到"<<endl;
    }//else
    return 0;
}

原文链接：Finding the Minimum Window in S which Contains All Elements from T

<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>