JAVA DP solution


  • 0
    T
        public class Solution {
        public int[][] table;
        public int minDistance(String word1, String word2) {
            if(word2.length()==0) return word1.length();
            if(word1.length()==0) return word2.length();
            table=initialTable(word1.length(),word2.length());
            return findMin(word1, word2, 0,0,word1.length());
        }
        
        
        int findMin(String word1, String word2, int x1, int x2,int l1){
            if(x1==word1.length()) return word2.length()-l1;
            if(x2==word2.length()) return l1-x2;
            if(table[x1][x2]==-1){
                int count=0;
                if(word1.charAt(x1)==word2.charAt(x2)){
                    count=findMin(word1,word2,x1+1,x2+1,l1);
                }else{
                    //not equal
                    int countInsert=1+findMin(word1,word2,x1,x2+1,l1+1);
                    int countDel=1+findMin(word1,word2,x1+1,x2,l1-1);
                    int countRlc=1+findMin(word1,word2,x1+1,x2+1,l1);
                    count=min(countInsert,countDel,countRlc);
                }
            
                table[x1][x2]=count;
            }
            return table[x1][x2];
        }
        
        int min(int a,int b,int c){
            int tmpMin=Math.min(a,b);
            tmpMin=Math.min(tmpMin,c);
            return tmpMin;
        }
        
        int[][] initialTable(int l1,int l2){
            int[][] table=new int[l1][l2];
            for(int i=0;i<l1;i++){
                for(int j=0; j<l2;j++){
                    table[i][j]=-1;
                }
            }
            return table;
        }
    }
    

    Hope this is easy to understand.
    Basically consider all the case, pretend that we insert/replace/delete word1 by only changing its expected length. And count the num of operations.
    Then use a table to store the intermediate results


Log in to reply
 

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