LeetCode 727. 最小窗口子序列
题目描述
题意分析
在源串
s中找最短的连续窗口，使目标串t是这个窗口的子序列：目标字符可以不相邻，但相对顺序必须一致。若最短窗口有多个，返回起点最靠左的一个；不存在则返回空字符串。下面按非空目标串进行匹配。
解法：双指针扫描 + 回溯收缩
核心思路
[!blue]
先从当前起点
i向右扫描，用k表示已匹配的目标字符数。遇到下一个需要的字符就立即匹配，因为越早完成这一位，留给后面目标字符的空间越多，不会妨碍后续匹配。首次匹配完目标时，就找到了从i开始能达到的最早终点。这个终点已确定，但正向匹配时的起点可能偏早。于是固定终点，从目标最后一个字符开始向左倒序匹配，每次取尽量靠右的位置。它给更前面的目标字符留下更多可选位置，并最终得到最靠右的合法起点
start，所以当前窗口已不能再从左侧缩短。记录窗口后，从
start + 1重新开始。被跳过的更早起点无需重试：本轮终点之前不可能完成匹配；如果改用同样或更晚的终点，又从start或更早位置开始，窗口只会相同或更长。只有比start更晚的起点才可能产生更优答案。新一轮若扫描到源串末尾仍无法匹配完整目标，后面更短的后缀也不可能匹配，可以直接结束。各轮候选起点严格右移，只有窗口严格变短时才更新答案，就能在长度相同时保留最靠左的候选。
解题步骤
- 初始化搜索起点
i = 0，以及表示尚无答案的bestStart = -1。- 从
j = i正向扫描，用k按顺序匹配目标。若末尾仍未匹配完，结束整个搜索。- 匹配完成时，
j指向窗口右端后一格。从end = j - 1向左倒序匹配目标，直到匹配到目标首字符。- 反向扫描结束后，代码中的
end已移动到窗口起点，令start = end，窗口长度为j - start。- 若长度严格小于已知最短值，保存长度和起点；再令
i = start + 1，继续搜索。- 没有找到过窗口就返回空字符串，否则按保存的起点和长度截取结果。
代码实现
// 然后向左回溯，尽量收缩窗口以得到最短左边界。
class Solution {
public String minWindow(String s, String t) {
int n = s.length();
int m = t.length();
int bestLen = Integer.MAX_VALUE;
int bestStart = -1;
int i = 0;
while (i < n) {
int j = i;
int k = 0;
while (j < n && k < m) {
if (s.charAt(j) == t.charAt(k)) {
k++;
}
j++;
}
// 剩余后缀已不能完成匹配，更靠右起点也无解
if (k < m) {
break;
}
// 固定最早匹配终点，反向寻找最靠右的合法起点
int end = j - 1;
k = m - 1;
while (end >= i) {
if (s.charAt(end) == t.charAt(k)) {
k--;
if (k < 0) {
break;
}
}
end--;
}
int start = end;
int len = j - start;
if (len < bestLen) {
bestLen = len;
bestStart = start;
}
// 越过已经收紧的起点，避免重复考察被支配窗口
i = start + 1;
}
if (bestStart == -1) {
return "";
}
return s.substring(bestStart, bestStart + bestLen);
}
}
// 然后向左回溯，尽量收缩窗口以得到最短左边界。
func minWindow(s string, t string) string {
n := len(s)
m := len(t)
bestLen := n + 1
bestStart := -1
i := 0
for i < n {
j := i
k := 0
for j < n && k < m {
if s[j] == t[k] {
k++
}
j++
}
// 剩余后缀已不能完成匹配，更靠右起点也无解
if k < m {
break
}
// 固定最早匹配终点，反向寻找最靠右的合法起点
end := j - 1
k = m - 1
for end >= i {
if s[end] == t[k] {
k--
if k < 0 {
break
}
}
end--
}
start := end
length := j - start
if length < bestLen {
bestLen = length
bestStart = start
}
// 越过已经收紧的起点，避免重复考察被支配窗口
i = start + 1
}
if bestStart == -1 {
return ""
}
return s[bestStart : bestStart+bestLen]
}
复杂度分析
- 时间复杂度：$O(nm)$，其中 $n$、$m$ 为源串与目标串长度。起点右移后，在同一个源位置之前能匹配的目标前缀不会变长；若该位置被再次扫描，匹配进度还必须严格减少。否则可以复用上一轮从这里到旧终点的剩余匹配，在更晚起点完成旧终点的匹配，与反向求得“最靠右的起点”矛盾。进度只有
0到m - 1，所以每个源位置最多被正向检查 $m$ 次；每轮反向扫描不长于该轮正向扫描，总量仍是 $O(nm)$。- 空间复杂度：$O(1)$，只保存扫描下标与最佳窗口信息，不计返回字符串。
关键点总结
[!green]
- 正向贪心找最早完成点，反向贪心找这个终点对应的最晚起点。
- 从收紧后的起点加一继续，跳过的是已经被当前窗口覆盖的更差选择。
j始终保留右端后一格的位置，所以长度直接是j - start。
易错点总结
[!yellow]
- 字符数量足够不代表子序列匹配成功，正向和反向都必须维护目标字符顺序。
- 只有完整匹配后才能反向收缩，否则找不到合法的目标首字符位置。
- 反向目标下标减到负数后必须结束，不能继续访问目标串。
- 后续搜索应从
start + 1开始，直接跳到窗口终点之后会漏掉重叠的更短窗口。- 长度相等时也替换答案，会把先找到的最左窗口覆盖掉。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 392. 判断子序列 | 简单 | 子序列匹配是基础，本题还需比较所有可行匹配覆盖的区间长度。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！