给出 S 字符串和 T 字符串。找到 S 字符串中包含 T 所有字符的最短字符串,或最小窗口。
解题思路分五个步骤。分别是
- 记录 T 字符出现次数的 HashMap,和出现次数 count。
- 声明两个指针 start 和 end,都初始化 0 并右移 end,直至 count = 0。
- 此刻 start < “string” < end 是 S 部分字符串,但已包含 T 的所有字符。
String S |
A |
D |
D |
B |
A |
N |
C |
A |
D |
|
start |
|
|
|
|
|
|
end |
|
- 右移 start,直至 count > 0。
- 此刻 start < “string” < end 不再包含所有 T 字符。
- 记录 start 前一个位置 minStart,和 end 的位置 minEnd,即包含所有 T 字符的情况。
String S |
A |
D |
D |
B |
A |
N |
C |
A |
D |
|
|
|
|
minStart |
start |
|
minEnd |
end |
|
- 右移 end,在得到 count = 0 之前到达尽头停止循环,否则可重复二三步操作。
String S |
A |
D |
D |
B |
A |
N |
C |
A |
D |
|
|
|
|
minStart |
start |
|
|
minEnd |
end |
- 当循环终止,minStart ≤ “string” < minEnd (前开后闭)即最小窗口。
String S |
A |
D |
D |
B |
A |
N |
C |
A |
D |
|
|
|
|
minStart |
|
|
|
minEnd |
|
上述过程采用思路类似“滑动窗口”。