LeetCode: Minimum Window Substring

LeetCode: 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.

地址：https://oj.leetcode.com/problems/minimum-window-substring/

算法：由于申请两个大小为256的数组，用于统计每一个字符串中各字母的个数，然后用isWindow函数来判断是否由hashS表示的字符串包含由hashT表示的字符串。首先，从S开始找到第一在T中出现的字母位置，记为i，初始化start为i，其中count表示在字符串S[start~i]之间出现在字符串T的字符个数。在每次进入循环时都判断S[start~i]是否可以包含T，如果包含，则根据情况更新最小窗口，并且更新start为下一个出现在字符串T中位置（因为最小的窗口的其实位置一定会出现在字符串T中），注意还要将改变hashS让其表示当前的S[start~i]（注意i还是不变）；如果不包含，则改变i为下一个出现在字符串T中的位置，并且同时更新对应的hashS。代码：

 1 class Solution {
 2 public:
 3     string minWindow(string S, string T) {
 4         int slen = S.size();
 5         int tlen = T.size();
 6         if(slen <= 0 || tlen <= 0)   return string();
 7         vector<int> hashT(256,0);
 8         vector<int> hashS(256,0);
 9         for(int i = 0; i < tlen; ++i)
10             ++hashT[T[i]];
11         int minNum = slen + 1;
12         int minStart = 0, minEnd = 0;
13         int i = 0;
14         while(i < slen && !hashT[S[i]]){
15             ++i;
16         }
17         if(i >= slen)   return string();
18         int start = i;
19         int count = 1;
20         ++hashS[S[i]];
21         while(i < slen){
22             if(isWindow(hashT,hashS,count,tlen)){
23                 if(minNum > i-start+1){
24                     minNum = i-start+1;
25                     minStart = start;
26                     minEnd = i;
27                 }
28                 --count;
29                 --hashS[S[start]];
30                 ++start;
31                 while(start<slen && !hashT[S[start]])   ++start;
32                 
33             }else{
34                 ++i;
35                 while(i<slen && !hashT[S[i]])   ++i;
36                 if(i < slen){
37                     ++count;
38                     ++hashS[S[i]];
39                 }
40             }
41         }
42         if(minNum == slen + 1){
43             return string();
44         }
45         return S.substr(minStart,minNum);
46     }
47     bool isWindow(vector<int> &hashT, vector<int> &hashS, int count ,int tlen){
48         if(count < tlen)
49             return false;
50         for(int i = 0; i < 256; ++i){
51             if(hashS[i] < hashT[i]){
52                 return false;
53             }
54         }
55         return true;
56     }
57 };