首页 > 代码库 > 【leetcode】Minimum Window Substring
【leetcode】Minimum Window Substring
问题：
生活场景：
分析：
以我们列举的生活场景为例，我们在具体做这件事的时候，肯定不会拿着老板给的类似T中：A物品 B物品 A物品 C物品 这么二的清单，而是对物品做统计，生成这样的需求清单：
物品A：X件
物品B：Y件
物品C：Z件
而在寻找的过程中，我们还需要一份已收集清单，就是目前已经找到的每个物品的信息，其形式与上面列举的一致。那么这些信息怎么来存储呢，我们总是希望对给定的物品，在O(1)的时间内找出对应的数值信息，所以要用hash table。
我们开始在起始楼层(下电梯的楼层)向上查找，遇到一个物品，我们看下是否是我们需要的，若是，则收集，并更改已收集清单相应物品的数量上加1。若不是，则跳过，继续向楼上搜集。看到这里我们就发现了问题，因为我们看到物品是需要的就收集它，并更改已收集表，那么我们怎么判断我们已经完成了收集工作了呢？比较两个表中对于的项，已收集项都大于等于需求的时候？但这样要进行比较，不能在O(1)的时间得到明确的判断，所以我们还需要一个变量，来记录到目前为止，收集到的”有效“的物品数，何为有效的物品，比如需求里A：3，B：2，假设A的数量已经是3，当再次遇到A时，虽然A是需求清单里需要的，但是已经有3个了，满足要求了，现在遇到的A就不能算作有效的物品，你现在需要做的是去收集除A以外其他物品。当有效物品数与需求清单中的总物品数相等的时候，我们就说我们的收集工作完成了。
但是这时你又会想，有没有更好的选择，比如你是从1楼开始收集的，收集到10楼将物品收集完毕，从2楼或者更高的楼层开始收集是不是也能完成任务？这样就可以少爬几层楼梯。这就要判断1楼的物品性质了，假如1楼的物品不是需要的，当然可以直接从2楼开始，亦或者，虽然1楼的物品是需要的，但是2楼也有这个物品，而且从2楼开始，这个物品总是也满足要求。那么就可以从2楼开始，依次2楼，3楼，直到不能精简，这就是当前的一个精简窗口，也就是不包含子窗口的窗口。但这个就是最小的吗？不一定，因为可能从11楼开始，到13楼就收集齐备了。所以这个查找的过程要进行到最后。每次找到新的窗口，跟目前最小的比较，更新最小窗口。
实现：
string minWindow(string S, string T) {
int N = S.size();
int M = T.size();
int minWindowLen = INT_MAX;
//hash table init all 0s
//used to statistic the number of each letter needed.
int needToFind[256] = {0};
for (int i = 0; i < M; ++i)
needToFind[T[i]]++;
//hash table init all 0s
//used to record the number of each letter has found.
int hasFind[256] = {0};
//use to record the total letters we has found.
//if it equal to T.size(), it means we get a window.
int count = 0;
// end used to find the letters needed in T.
// start used to drop the redundant letters to cut short the window.
int start, end;
//min_start and min_end recored the optimal resolve.
int min_start = 0;
int min_end = INT_MAX;
for (start = 0, end = 0; end < N; ++end)
{
if( 0 == needToFind[ S[end] ])//not needed
continue;
hasFind[ S[end] ]++;
if(hasFind[ S[end] ] <= needToFind[ S[end] ])
count++;
//find a window
if(count == M){
//judge whether the window can be cut short, for example,
//the letter indicated by start is not needed or redundant.
while ( 0 == needToFind[ S[start] ] || hasFind[S[start]] > needToFind[S[start]])
{
if(hasFind[S[start]] > needToFind[S[start]])//redundant
hasFind[S[start]]--;
++start;
}
int windowLen = end - start + 1;
if (windowLen < minWindowLen)
{
minWindowLen = windowLen;
min_start = start;
min_end = end;
}
}
}
if(min_end == INT_MAX)
return "";
return S.substr(min_start, min_end - min_start + 1);
}