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.
这道题的要求是在给定的字符串S中找到最小的窗口使其完全包含字符串T中所有字符，如果不存在，则返回空串”“。
和Longest Substring Without Repeating Characters及Substring with Concatenation of All Words类似的思路，使用l和r两个指针维护子串，用Hash表记录T字串中出现的字符。S中，每次循环r右移1位，然后判断r右移之后所指向的字符是否在Hash表中出现过：如果出现过，则表示在T中。此时通过计数器cnt判断T中字符是否都出现过，如果是，则记录l和r之间子串长度，并与最短长度比较。然后逐步右移l并在Hash表中删除l指向的字符直到计数器cnt小于T中字符数量。
注意一下，由于T中同一字符的数量可能减到负值，因此需要2重判断：先判断是否出现此字符，在判断此字符出现的具体数量。
时间复杂度：O(l1+l2)（l1和l2分别为字符串S和T的长度）
空间复杂度：O(l2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution
{
public:
string minWindow(string S, string T)
{
// 用Hash表记录T中字符
unordered_map<char, int> m;
for(int i = 0; i < T.size(); ++ i)
++ m[T[i]];
int cnt = 0, l = 0, minl = 0, minsize = S.size() + 1;
for(int r = 0; r < S.size(); ++ r)
if(m.find(S[r]) != m.end())
{
if(-- m[S[r]] >= 0)
++ cnt;
while(cnt == T.size())
{
if(r - l + 1 < minsize)
minl = l, minsize = r - l + 1;
if(m.find(S[l]) != m.end())
if(++ m[S[l]] > 0)
-- cnt;
++ l;
}
}
if(minsize > S.size())
return "";
return S.substr(minl, minsize);
}
};
由于字符是ASCII，因此可以用char[128]的数组代替unordered_map做Hash表，经测试，速度有明显提升。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution
{
public:
string minWindow(string S, string T)
{
int c[128] = {0};
bool flag[128] = {false};
for(int i = 0; i < T.size(); ++ i)
{
flag[T[i]] = true;
++ c[T[i]];
}
int cnt = 0, l = 0, minl = 0, minsize = S.size() + 1;
for(int r = 0; r < S.size(); ++ r)
if(flag[S[r]])
{
if(-- c[S[r]] >= 0)
++ cnt;
while(cnt == T.size())
{
if(r - l + 1 < minsize)
minl = l, minsize = r - l + 1;
if(flag[S[l]])
if(++ c[S[l]] > 0)
-- cnt;
++ l;
}
}
if(minsize > S.size())
return "";
return S.substr(minl, minsize);
}
};