Java 169ms DP (S*T) Solution, I tried my best to make it easy to understand


  • 0
    W
    class Solution {
        public String minWindow(String S, String T) {
            int[][] dp = new int[S.length()+1][T.length()+1];
            for (int i = 0; i < dp.length; Arrays.fill(dp[i++], -1));
            for (int i = 1; i <= S.length(); i++) 
                if (S.charAt(i-1) == T.charAt(0))
                    dp[i][1] = i-1; 
                else
                    dp[i][1] = dp[i-1][1];
            
            for (int j = 2; j <= T.length(); j++) {
                for (int i = 1; i <= S.length(); i++) {
                    if (S.charAt(i-1) == T.charAt(j-1))
                        dp[i][j] = dp[i-1][j-1];
                    else
                        dp[i][j] = dp[i-1][j];
                }
            }
            String ret = "";
            for (int i = 1; i <= S.length(); i++)
                if (dp[i][T.length()] != -1)
                    if (ret.equals("") || ret.length() > i - dp[i][T.length()])
                        ret = S.substring(dp[i][T.length()], i);
            return ret;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.