题目描述

给定两个串S和T，在S中找一个最小子串W，满足T是W的子序列。如果有个最小子串W满足要求，则返回最左边的那个。

样例

Input: 
S = "abcdebdde", T = "bde"
Output: "bcde"

Explanation: 
"bcde" "bdde" 都是满足条件的W，但"bcde"出现在"bdde"之前，因此返回"bcde"

算法1

动态规划 $O(|S|*|T|)$

建立一个二维dp数组，大小为|S|*|T|。dp[i][j]表示S的(0~i)子串和T的(0~j)所对应最小W的长度

对S和T中的每个位置进行匹配：
1. 如果S[i]!=T[j]，则dp[i][j] = dp[i-1][j]+1。
2. 如果S[i]==T[j], 则dp[i][j] = max(dp[i-1][j]+1, dp[i-1][j-1]+1)

最后遍历dp[i][len(T)]，求出第一个最小的值ans和ans对应的i，S中从i-ans到i的的子串即为所求

时间复杂度分析：对S和T中的每个位置进行计算，时间复杂度$O(|S|*|T|)$

Java 代码

class Solution {
    public String minWindow(String S, String T) {
        int ns=S.length(), nt=T.length();
        int[][] dp = new int[ns+1][nt+1];
        for(int j=1; j<=nt; j++) dp[0][j]=Integer.MAX_VALUE/10;

        for(int i=1; i<=ns; i++) {
            for(int j=1; j<=nt; j++) {
                if(S.charAt(i-1)!=T.charAt(j-1)) dp[i][j] = dp[i-1][j]+1;
                else dp[i][j] = Math.min(dp[i-1][j]+1, dp[i-1][j-1]+1);
            }
        }

        int ans=Integer.MAX_VALUE, k=-1;
        for(int j=1; j<=ns; j++) {
            if(ans>dp[j][nt]) {
                ans = dp[j][nt]; k=j;
            }
        }
        if(ans>=Integer.MAX_VALUE/10) return "";
        return S.substring(k-ans, k);
    }
}