线性动态规划：最小窗口子序列

题目描述
给定字符串 s 和 t，找出 s 中最短的子串，使得 t 是该子串的子序列。如果不存在这样的子串，返回空字符串。如果有多个最短子串，返回最靠左的一个。

示例

• 输入：s = "abcdebdde", t = "bde"
• 输出："bcde"
• 解释：在 "abcdebdde" 中，"bcde" 是包含子序列 "bde" 的最短窗口（"bdde" 也是，但更长）。

解题思路

1. 问题分析

我们需要在 s 中找到一个子串，其子序列为 t，且长度最小。
关键点：子序列不要求连续，但子串是连续的。因此，我们需要在 s 的连续子串中匹配 t 作为子序列。

2. 动态规划定义

定义 dp[i][j] 表示匹配到 t 的前 j 个字符时，在 s 中以 i 结尾的窗口的起始位置。

• 若 dp[i][j] = k，表示 s[k:i+1] 包含 t[0:j] 作为子序列，且 k 是满足条件的最小起始索引。

3. 状态转移

• 当 s[i] == t[j]：
  • 如果 j == 0（匹配第一个字符），则窗口起始位置就是 i：dp[i][0] = i。
  • 如果 j > 0，则需要依赖前一个状态 dp[i-1][j-1]。窗口起始位置继承自 dp[i-1][j-1]：
    dp[i][j] = dp[i-1][j-1]。
• 当 s[i] != t[j]：
  • 如果 j == 0，无法匹配，设为无效值（如 -1）。
  • 如果 j > 0，则继承同一行前一列的状态（即当前字符不匹配，但前一段可能已匹配）：
    dp[i][j] = dp[i-1][j]。

4. 窗口长度计算

遍历 dp[i][len(t)-1]，找到所有有效的窗口 [start, i]，计算长度 i - start + 1，取最小值。

详细步骤

1. 初始化

   • 创建二维数组 dp，尺寸 len(s) × len(t)，初始化为 -1（表示无效）。
   • 遍历 i 从 0 到 len(s)-1，j 从 0 到 len(t)-1。

2. 填充 dp 数组

   • 若 s[i] == t[j]：
     • j == 0：dp[i][0] = i
     • j > 0：若 i > 0 且 dp[i-1][j-1] != -1，则 dp[i][j] = dp[i-1][j-1]，否则为 -1。
   • 若 s[i] != t[j]：
     • j > 0 且 i > 0：dp[i][j] = dp[i-1][j]（继承前一行的匹配状态）。

3. 查找最小窗口

   • 遍历每个 i，若 dp[i][len(t)-1] != -1，则窗口长度为 i - dp[i][len(t)-1] + 1。
   • 记录最小长度及对应的起始和结束索引。

4. 返回结果

   • 若找到有效窗口，返回 s[start:end+1]，否则返回空字符串。

示例推导（s = "abcdebdde", t = "bde"）

1. 初始化 dp（行对应 s，列对应 t）：

       b  d  e
   a   -1 -1 -1
   b   1  -1 -1
   c   1  -1 -1
   d   1  1  -1
   e   1  1  1  → 窗口 "bcde" 长度 4
   b   5  -1 -1
   d   5  5  -1
   d   5  5  -1
   e   5  5  5  → 窗口 "bdde" 长度 4
   

2. 比较窗口：第一个有效窗口 "bcde" 起始索引 1，结束索引 4，长度 4；第二个 "bdde" 长度也是 4，但靠右，故最终输出 "bcde"。

算法优化

• 空间优化：dp 数组可降为一维，只保存前一行的状态。
• 提前终止：在匹配完 t 的最后一个字符时立即记录窗口，避免全表遍历。

复杂度分析

• 时间复杂度：O(n × m)，其中 n = |s|, m = |t|。
• 空间复杂度：O(m)（优化后）。