区间动态规划例题：最小窗口子序列问题（字符串匹配最小窗口） 题目描述 给定一个字符串S和一个字符串T，找出S中包含T所有字符的最短连续子串（窗口）。如果S中不存在这样的子串，返回空字符串。注意：T中可能有重复字符，且窗口需要包含T中每个字符的相应次数（即完全匹配T的字符频率）。 例如： S = "ADOBECODEBANC", T = "ABC" 输出应为 "BANC"，因为它是S中包含A、B、C的最短连续子串。 解题思路 这是一个经典的字符串匹配问题，但我们可以用动态规划（特别是区间DP的思路）来高效解决。核心思想是预处理S中每个字符位置对T中字符的匹配信息，然后利用这些信息快速找到包含T的最短窗口。 步骤详解 步骤1：预处理字符出现位置 创建一个二维数组 next[i][c] ，表示在S的位置i之后，字符c下一次出现的位置。 初始化：从S的末尾开始向前遍历，记录每个字符最近出现的位置。 对于每个位置i和每个字符c， next[i][c] 存储从i开始（包括i）下一个c出现的位置。如果i位置就是c，则 next[i][c] = i ；否则 next[i][c] = next[i+1][c] （如果存在）。 示例（S="ADOBECODEBANC", T="ABC"）： 对于字符'A'，在位置0、5、10出现。 next[0]['A'] = 0 , next[1]['A'] = 5 , 等等。 步骤2：匹配T的每个字符 对于T中的每个字符，我们需要在S中找到匹配的位置。利用 next 数组，我们可以快速定位。 具体操作：从S的每个起始位置i开始，尝试匹配T。用 start 表示当前窗口起始， j 表示当前匹配到T的第几个字符。 初始化 j=0 ，当前指针 cur = i 。 对于T的每个字符 T[j] ，通过 next[cur][T[j]] 找到下一个匹配位置。如果找不到（值为-1），则从i起始无解。 如果找到，更新 cur = next[cur][T[j]] + 1 （移动到匹配字符的下一个位置），继续匹配T的下一个字符。 步骤3：记录最短窗口 对于每个起始位置i，如果成功匹配完T的所有字符，则得到一个窗口[ i, end ]，其中end是最后一个匹配字符的位置。 比较所有成功窗口的长度，记录最短的窗口起始和结束位置。 示例运行： 从i=0开始：匹配T[ 0]='A'，在位置0找到A；匹配T[ 1]='B'，从位置1开始找B，在位置3找到；匹配T[ 2]='C'，从位置4开始找C，在位置5找到。窗口为[ 0,5 ]，长度6。 从i=1开始：匹配T[ 0]='A'，从位置1找A，在位置5找到；匹配T[ 1]='B'，从位置6找B，在位置9找到；匹配T[ 2]='C'，从位置10找C，在位置10找到。窗口为[ 5,10 ]，长度6。 从i=5开始：匹配T[ 0]='A'，在位置5找到；匹配T[ 1]='B'，从位置6找B，在位置9找到；匹配T[ 2]='C'，从位置10找C，在位置10找到。窗口为[ 5,10 ]，长度6。 从i=9开始：匹配T[ 0]='A'，从位置9找A，在位置10找到；匹配T[ 1 ]='B'，从位置11找B，找不到，无解。 从i=10开始：匹配T[ 0]='A'，在位置10找到；匹配T[ 1 ]='B'，找不到，无解。 最短窗口为[ 9,12 ]（"BANC"），长度4。 复杂度分析 预处理 next 数组：O(len(S) * 字符集大小)，字符集大小可视为常数。 匹配过程：最多检查len(S)个起始点，每个起始点匹配T需O(len(T))，总O(len(S)* len(T))。 优化：实际中，通过预处理，匹配T可快速跳过，接近O(len(S))。 关键点 预处理 next 数组是效率提升的关键，避免了每次匹配都扫描整个S。 动态规划的思想体现在预处理阶段，通过递推计算每个位置的匹配信息。 窗口的滑动通过起始点的遍历实现，确保不漏解。 通过以上步骤，我们就能高效找到S中包含T的最短窗口。这个方法比暴力搜索高效得多，适用于较长的字符串。