LeetCode 727. 最小窗口子序列

Categories:

题目描述
思路分析
1. 解法一：双指针扫描 + 回溯收缩（推荐）
相似题目

题目描述

✅ 727. 最小窗口子序列

思路分析

解法一：双指针扫描 + 回溯收缩（推荐）

核心思路：

用指针在 s 中寻找 t 的子序列，第一次匹配到结尾得到右边界。

然后向左回溯，尽量收缩窗口以得到最短左边界。

重复该过程，取全局最短窗口。

复杂度分析：

时间复杂度：O(n * m)，其中 n、m 分别表示 s 和 t 的长度。

空间复杂度：O(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;

            // 向右找到 t 的子序列
            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;
        }

        return bestStart == -1 ? "" : 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

		// 向右找到 t 的子序列
		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]
}

相似题目

题目	难度	考察点
76. 最小覆盖子串	困难	双指针
392. 判断子序列	简单	双指针
1092. 最短公共超序列	困难	DP
1143. 最长公共子序列	中等	DP
583. 两个字符串的删除操作	中等	DP

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/66376032