[算法系列之二十二]包含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全部元素的最小子窗口* 来源：算法系列* 博客：———————————————–*/;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;}needFind[256] = {0};for(int i = 0;i < tlen;++i){++needFind[t[i]];}(int i = 0; i < 256;++i){if(needFind[i] == 0){needFind[i] = -1;}//if}//forint 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;}(q[val].size() < needFind[val]) {q[val].push(i);m[i] = val;}{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);}//elseif(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}//forreturn (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;}//ifelse{cout<<“未找到”<<endl;};}

O(N)方法：

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

青春一经典当即永不再赎