leetcode Minimum Window Substring(最短摘要算法)分析和题解

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

一个最短摘要算法的简化版本。

用到滑动窗口的概念。整个算法的运行过程可通过下图表示,注意仔细体会!

滑动窗口产生最短摘要

注意

在上图中灰色部分,当窗口中出现了所有目标字符后,需要从窗口的最左边开始往右滑动窗口边界,将左边窗口中多出来的目标字符移到窗口外,从而找到一个备选的最短窗口!

这个题较难,值得好好理解。

具体C++代码如下:

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
// 最短摘要生成算法
char* minWindow(char* s, char* t) {
if(s == NULL || t == NULL)
return "";

char c;
int sizeT = strlen(t);
int sizeS = strlen(s);
char *result = (char *)malloc(sizeof(char)*(sizeS+1));
int start, end;
int findAll = 0;
int minLen = sizeS + 1;
int minStart, minEnd;

int needToFind[128] = {0};
int hasFound[128] = {0};

for(start = 0; start < sizeT; start++)
{
needToFind[t[start]] ++;
}

start = 0;
end = 0;
while(end < sizeS)
{
c = s[end];

if(needToFind[c])
{
hasFound[c] ++;

if(hasFound[c] <= needToFind[c]) // 在找到一个可行解后,该if语句不会再满足!!!!
findAll ++;

if(findAll == sizeT)
{
while(needToFind[s[start]] == 0 || hasFound[s[start]] > needToFind[s[start]]) // 滑动窗口
{
if(hasFound[s[start]] > needToFind[s[start]])
hasFound[s[start]] --;

start ++;
}

if(minLen > (end-start+1))
{
minLen = end-start+1;
minStart = start;
minEnd = end;
}
// findAll = 0; !!!!! findAll并没有重新初始化为0
}
}

end ++;
}

if(minLen == sizeS+1)
return "";
else
{
start = 0;
for(end = minStart; end <= minEnd; end ++)
{
result[start] = s[end];
start ++;
}
result[start] = '\0';
return result;
}
}