leetcode727
最小窗口子序列
题目描述：
给定字符串 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"
输出：""
|
代码实现：
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;
}
}
|
思路 ：
用滑动窗口去做，遍历s1串，如果s2到了末尾（p2 == l2)，进行回溯寻找起点。
几个注意点：
i. 因为先做p2++，所以末尾的判断条件是 p2 == l2， 而不是p2 == l2 - 1,此时p1还没加1，还在最后一个字符位置。
ii. 进行回溯后，p1指向的位置是第一个字符的前一个位置，所以要加1。
iii. 要维护一个min变量，判断这个长度是不是最小的，如果是，就动态更新res的值。
iv. 因为p1的坐标进行了回溯，最后又加1了，所以下一次遍历是从s1的下一个字符开始的。s1确实需要进行遍历，因为要找到最小的子串。