Java Dyanmic Programming Solution


  • 0
    A
        public int minDistance(String word1, String word2) {
    
              int lenWord1, lenWord2;
    
            lenWord1 = word1.length();
            lenWord2 = word2.length();
            int k = 0, m = 0;
            int count = 0;
            int maxLen = 0;
            int answerSet = 0;
            int doubleDim [] [] = new int [lenWord1+1][lenWord2+1];
            int temp;
    
    
            for (int i = 0; i<=lenWord1;i++){
                for(int j = 0;j <=lenWord2;j++){
                    if(i == 0){
                        doubleDim[i][j] = 0;
                        continue;
                    }
                    if(j == 0){
                        doubleDim[i][j] = 0;
                        continue;
                    }
    
                    if(word1.charAt(i-1) == word2.charAt(j-1)){
                        temp = 1 + doubleDim[i-1][j-1];
                        doubleDim[i][j] = temp;
                    }else{
                        temp = Integer.max(doubleDim[i-1][j],doubleDim[i][j-1]);
                        doubleDim[i][j] = temp;
             
                    }
    
                }
             
            }
    
            maxLen = doubleDim[lenWord1][lenWord2];
            answerSet = lenWord1 + lenWord2 - 2*maxLen;
            return answerSet;
        }
    }

Log in to reply
 

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