EZ java iterative DP solution with explanations


  • -1
    M
    public int minDistance(String word1, String word2) {
        if(word1 == "" && word2 == "" return 0;
        if(word1 == "") return word2.length();
        if(word2 == "") return word1.length();
        
        int row = word1.length() + 1, col = word2.length() + 1;
        // ans[i][j] means the minimum steps that transfer word1.substring(1,i) to word2.substring(1,j),lets assume that the index start from 1//
        int[][] ans = new int[row][col]; 
        // transfer word1.substring(1,i) to "" needs i steps;//
        for(int i = 0 ; i < row ; i++){
            ans[i][0] = i;
        }
        // transfer "" to word2.substring(1,j) needs j steps;//
        for(int j = 0 ; j < col ; j++){
            ans[0][j] = j;
        }
        
        for(int i = 1 ; i < row ; i++){
            for(int j = 1; j < col ; j++){
                int a = ans[i][j-1] + 1;// steps of inserting a letter//
                int b = ans[i-1][j] + 1;// steps of deleting a letter// 
                int c = word1.charAt(i-1) == word2.charAt(j-1) ? ans[i-1][j-1] : ans[i-1][j-1] + 1;//steps of replacing a letter//
                ans[i][j] = Math.min(a,Math.min(b,c));
            }
        }
        return ans[row-1][col-1];
    }

Log in to reply
 

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