share Java DP solution!


  • 1
    T
    class Solution {
        public String minWindow(String S, String T) {
            if(T.length()>S.length()){
                return "";
            }
            int[][] dp = new int[T.length()][S.length()];
            for(int i=0;i<dp.length;i++){
                Arrays.fill(dp[i],-1);
            }
            for(int i=0;i<S.length();i++){
                if(S.charAt(i)==T.charAt(0)){
                    dp[0][i] = i;
                }else if(i>0){
                    dp[0][i] = dp[0][i-1];
                }
            }
            
            for(int i=1;i<T.length();i++){
                for(int j=i;j<S.length();j++){
                    if(T.charAt(i)==S.charAt(j)){
                        dp[i][j] = dp[i-1][j-1];
                    }else{
                        dp[i][j] = dp[i][j-1];
                    }
                }
            }
            int min_len = Integer.MAX_VALUE;
            int min_index = -1;
            for(int i=0;i<S.length();i++){
                if(T.charAt(T.length()-1)==S.charAt(i) && dp[T.length()-1][i]!=-1){
                    int start_index = dp[T.length()-1][i];
                    if(i-start_index+1<min_len){
                        min_len = i-start_index+1;
                        min_index = start_index;
                    }
                }
            }
            
            if(min_index==-1){
                return "";
            }
            
            return S.substring(min_index,min_index+min_len);
        }
    }
    

Log in to reply
 

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