Other solution, DP, concise


  • 0
    N

    class Solution {
    static int MIN = 1000000;
    public String minWindow(String S, String T) {
    int lenS = S.length(), lenT = T.length();
    int[][] dp = new int[lenT + 1][lenS + 1];
    for(int i = 0; i < dp.length; i++) Arrays.fill(dp[i], MIN);
    Arrays.fill(dp[lenT], 0);
    for(int i = lenT - 1; i >= 0; i--){
    for(int j = lenS - 1; j >= 0; j--){
    if(T.charAt(i) == S.charAt(j)){
    dp[i][j] = 1 + dp[i + 1][j + 1];
    }else{
    dp[i][j] = 1 + dp[i][j + 1];
    }
    }
    }
    int min = MIN, l = 0, r = 0;
    for(int i = 0; i < lenS; i++){
    if(dp[0][i] < min){
    min = dp[0][i]; l = i; r = i + min;
    }
    }
    if(min == MIN) return "";
    return S.substring(l, r);
    }
    }


Log in to reply
 

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