最小窗口子序列问题 问题描述： 给定字符串 S 和 T，在 S 中寻找最短的子串（连续子序列），使得该子串包含 T 的所有字符（按顺序但不一定连续）。返回这个最短子串的长度。如果不存在这样的子串，返回 -1。 示例： S = "abcdebdde", T = "bde" 最短子串是 "bcde"（包含 b, c, d, e 按顺序），长度为 4 解题过程： 问题分析 我们需要在 S 中找到包含 T 所有字符的最短连续子串 T 中的字符必须按顺序出现在子串中，但不要求连续 这是一个字符串匹配问题，可以使用区间动态规划解决 动态规划定义 定义 dp[ i][ j ] 表示：在 S 的前 i 个字符中，匹配 T 的前 j 个字符时，匹配子串的起始位置 状态转移方程： 如果 S[ i-1] == T[ j-1 ]： 当 j == 1 时：dp[ i][ 1 ] = i-1（从当前字符开始） 当 j > 1 时：dp[ i][ j] = dp[ i-1][ j-1 ]（继承前一个匹配的起始位置） 如果 S[ i-1] != T[ j-1 ]： dp[ i][ j] = dp[ i-1][ j ]（起始位置不变） 算法步骤 步骤1：初始化 创建 dp 数组，大小为 (m+1) × (n+1)，其中 m = len(S), n = len(T) 初始化所有值为 -1，表示无法匹配 步骤2：填充DP表 遍历 i 从 1 到 m（S 的每个字符）： 遍历 j 从 1 到 n（T 的每个字符）： - 如果 S[ i-1] == T[ j-1 ]： * 如果 j == 1：dp[ i][ j ] = i-1 * 否则：dp[ i][ j] = dp[ i-1][ j-1 ] - 否则： * dp[ i][ j] = dp[ i-1][ j ] 步骤3：寻找最短窗口 遍历 i 从 1 到 m： 如果 dp[ i][ n] != -1： 窗口长度 = i - dp[ i][ n ] 更新最小长度 详细示例演示 以 S = "abcdebdde", T = "bde" 为例： 初始化 dp 表（3×10）： i=0: [ -1,-1,-1 ] i=1: [ 0,-1,-1] (S[ 0]='a'匹配T[ 0 ]='b'? 不匹配) ... 逐步计算： i=2, j=1: S[ 1]='b'匹配T[ 0]='b' → dp[ 2][ 1 ] = 1 i=3, j=2: S[ 2]='c'不匹配T[ 1]='d' → dp[ 3][ 2] = dp[ 2][ 2 ] = -1 i=4, j=2: S[ 3]='d'匹配T[ 1]='d' → dp[ 4][ 2] = dp[ 3][ 1 ] = 1 i=5, j=3: S[ 4]='e'匹配T[ 2]='e' → dp[ 5][ 3] = dp[ 4][ 2 ] = 1 窗口长度 = 5-1 = 4 ("bcde") 复杂度分析 时间复杂度：O(m×n)，其中 m 和 n 分别是 S 和 T 的长度 空间复杂度：O(m×n)，可以优化到 O(n) 边界情况处理 如果 T 为空字符串，返回 0 如果 S 比 T 短，直接返回 -1 如果找不到匹配，返回 -1 这种方法通过动态规划记录了匹配的起始位置，能够高效地找到包含目标序列的最短窗口。