Java DP O(ST) time and space complexity


  • 0
    J
        public String minWindow(String S, String T) {
            int slength = S.length();
            int tlength = T.length();
            boolean[][] dp = new boolean[slength+1][tlength+1];
            for(int i=0;i<slength;i++){
                dp[i][0]=true;
            }
            for(int i=1;i<slength+1;i++){
                for(int j=1;j<tlength+1;j++){
                    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];
                }
            }
            int end = -1;
            int start = -1;
            int min = Integer.MAX_VALUE;
            for(int i=1;i<slength+1;i++){
                if(S.charAt(i-1)==T.charAt(tlength-1)&&dp[i][tlength]==true){
                   int curstart= find(S,T,dp,i);
                   if(i-curstart<min){
                       start = curstart;
                       end = i;
                       min = i-curstart;
                   }
                }
            }
            if(end<0) return "";
            return S.substring(start,end);
            
        }
        public int find(String S,String T,boolean[][] dp,int end){
            int count = 0;
            int start =end;
            int tlength = T.length();
            while(count<T.length()){
               if(dp[start-1][tlength-1]&&S.charAt(start-1)==T.charAt(tlength-1)){
                   start--;
                   tlength--;
                   count++;
               }else{
                   start--;
               }
            }
            return start;
        }
    

Log in to reply
 

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