My Accepted Java Solution


  • 24
    J

    Hi:

    This is a very interesting question and I found a youtube video that helps a lot.
    Basically the idea is to build up the solution step by step and keep track of the previous optimal solution in a 2D array. In this 2D array dp, dp[i][j] means the operation needed to transform word1(0, i) to word2(0,j).

    There can be three conditions:

    1, word1[i] == word2[j] : then no operation needed. dp[i][j] == dp[i-1][j-1]

    2, Do one operation on word1[i-1][j]. dp[i][j] = dp[i-1][j] + 1

    3, Do one operation on word2[i][j-1]. dp[i][j] = dp[i][j-1] + 1

    for 2 and 3, the reason it works is that we know the optimal ways to transfrom word1(0,i) to word2(0,j-1) and word1(0,i-1) to word(0,j) ( Delete ("abc" to "ab") or Insert ("ab" to "abc") ). Now all we need to one more operation.

    The code will be:

    public int minDistance(String word1, String word2) {
        if (word1.equals(word2)) {
            return 0;
        }
        if (word1.length() == 0 || word2.length() == 0) {
            return Math.abs(word1.length() - word2.length());
        }
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        for (int i = 0; i <= word1.length(); i++) {
            dp[i][0] = i;
        }
        for (int i = 0; i <= word2.length(); i++) {
            dp[0][i] = i;
        }
        for (int i = 1; i <= word1.length(); i++) {
            for (int j = 1; j <= word2.length(); j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) + 1;
                }
            }
        }
        return dp[word1.length()][word2.length()];
    }
    

    Remeber that we start from dp[0][0], which is an empty string to an empty string.


  • 0
    F

    Nice solution


  • 0
    C

    great explanation


  • 0
    M

    Nice! I think it is similar with LCS.


  • 0
    M

    Great explanation, however, I think when word1[i] == word2[j] :

    dp[i][j] == min(dp[i-1][j-1], dp[i-1][j] + 1, dp[i][j-1] + 1)
    

    Because "dp[i-1][j] + 1" or "dp[i][j-1] + 1" may less than "dp[i-1][j-1]".


  • 0
    S

    greate! your solution is easy to understand.


Log in to reply
 

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