最小窗口子序列
题目描述
给定字符串 s1 和 s2，找出 s1 中最短的连续 子串，使得 s2 是该子串的 子序列 。
如果 s1 中没有窗口可以包含 s2 中的所有字符，返回空字符串 ""。如果有不止一个最短长度的窗口，返回 开始位置最靠左 的那个。
示例 1
1
2
3
4
5
6
| 输入：
s1 = "abcdebdde", s2 = "bde"
输出："bcde"
解释：
"bcde" 是答案，因为它在相同长度的字符串 "bdde" 出现之前。
"deb" 不是一个更短的答案，因为在窗口中必须按顺序出现 T 中的元素。
|
示例 2
1
2
| 输入：s1 = "jmeqksfrsdcmsiwvaovztaqenprpvnbstl", s2 = "u"
输出：""
|
解题思路
用滑动窗口去做，遍历 s1 串，如果 s2 到了末尾（p2 == 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
| class Solution {
public String minWindow(String s1, String s2) {
int l1 = s1.length(), l2 = s2.length();
int p1 = 0, p2 = 0;
int min = l1 + 1;
String res = "";
while (p1 < l1) {
if (s1.charAt(p1) == s2.charAt(p2)) {
p2++;
}
if (p2 == l2) {
int r = p1;
while (p2 > 0) {
if (s1.charAt(p1) == s2.charAt(p2 - 1)) {
p2--;
}
p1--;
}
p1++;
if (r - p1 + 1 < min) {
min = r - p1 + 1;
res = s1.substring(p1, r + 1);
}
}
p1++;
}
return res;
}
}
|
注意点
- 因为先做
p2++，所以末尾的判断条件是 p2 == l2，而不是 p2 == l2 - 1，此时 p1 还没加 1，还在最后一个字符位置。
- 进行回溯后，
p1 指向的位置是第一个字符的前一个位置，所以要加 1。
- 要维护一个
min 变量，判断这个长度是不是最小的，如果是，就动态更新 res 的值。
- 因为
p1 的坐标进行了回溯，最后又加 1 了，所以下一次遍历是从 s1 的下一个字符开始的。s1 确实需要进行遍历，因为要找到最小的子串。