Java Solution with Time Complexity O(m*n) and Space Complexity O(2n)


  • 0
    S

    We can solve the problem with Time Complexity O(m*n) and Space Complexity O(2n). Look at minDistance3 method.
    We do not need to store all the rows. We just need to store the data of previous row. So maximum 2 rows of data at any point of time.

    class Solution {
        public int minDistance(String word1, String word2) {
            
          //  Time O(3^m), where m is the len of str1
          //  return minDistance(word1.toCharArray(), word2.toCharArray(), word1.length()-1, word2.length()-1);
          //  Time O(m*n) Space O(m*n)
          //  return minDistance2(word1.toCharArray(), word2.toCharArray());
          // Time O(m*n) Space O(m);
            return minDistance3(word1.toCharArray(), word2.toCharArray());
    
        }
        
        public int minDistance(char []w1,char []w2,  int i, int j){
            int count = 0;
            
            if( i == -1 && j == -1){
                return 0;
            }
            
            if( i == -1 ){
                return j+1;
            }
            
            if( j == -1 ){
                return i+1;
            }
            
    
            if(w1[i] == w2[j]){
                count = minDistance(w1,w2,i-1,j-1);
            }else{
                int insertCount = 1 + minDistance(w1,w2,i,j-1);
                int delCount = 1 + minDistance(w1,w2,i-1,j);
                int repCount = 1 + minDistance(w1,w2,i-1,j-1);
                count = Math.min(insertCount,Math.min(delCount, repCount));
            }
                
            return count;  
        }
        
        public int minDistance2(char []w1, char []w2){
            int i = w1.length;
            int j = w2.length;
            
            if( i == 0 && j == 0){
                return 0;
            }
            
            if( i == 0 ){
                return j;
            }
            
            if( j == 0 ){
                return i;
            }
            
            int [][]minDis = new int[i+1][j+1];
            
            for(int w1Indx = 0 ; w1Indx < i+1 ; w1Indx++){
    
                for(int w2Indx = 0; w2Indx < j+1; w2Indx++){
                    if(w1Indx == 0){
                        minDis[w1Indx][w2Indx] = w2Indx;
                        continue;
                    }
                    if(w2Indx == 0){
                        minDis[w1Indx][w2Indx] = w1Indx;
                        continue;
                    }      
                    if(w1[w1Indx-1] == w2[w2Indx-1]){
                         minDis[w1Indx][w2Indx] =  minDis[w1Indx-1][w2Indx-1];
                    }else{
                         minDis[w1Indx][w2Indx] = 1 + Math.min( minDis[w1Indx-1][w2Indx], Math.min(minDis[w1Indx][w2Indx-1], minDis[w1Indx-1][w2Indx-1]));
                    }
                }
            }
            return minDis[i][j];
        }
        
        public int minDistance3(char []w1, char []w2){
            int m = w1.length;
            int n = w2.length;
            
            if( m == 0 && n == 0){
                return 0;
            }
            
            if( m == 0 ){
                return n;
            }
            
            if( n == 0 ){
                return m;
            }
            
            int [][]minDis = new int[2][n+1];
            
            int dp = 0;
            
            for(int w1Indx = 0 ; w1Indx < m+1 ; w1Indx++){
                    dp = w1Indx & 1;
                for(int w2Indx = 0; w2Indx < n+1; w2Indx++){
                    if(w1Indx == 0){
                        minDis[dp][w2Indx] = w2Indx;
                        continue;
                    }
                    if(w2Indx == 0){
                        minDis[dp][w2Indx] = w1Indx;
                        continue;
                    }      
                    if(w1[w1Indx-1] == w2[w2Indx-1]){
                         minDis[dp][w2Indx] =  minDis[1-dp][w2Indx-1];
                    }else{
                         minDis[dp][w2Indx] = 1 + Math.min( minDis[1-dp][w2Indx], Math.min(minDis[dp][w2Indx-1], minDis[1-dp][w2Indx-1]));
                    }
                }
            }
            return minDis[dp][n];
        }
    }
    

Log in to reply
 

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