Java DP solution - O(nm)


  • 69
    W

    Let following be the function definition :-

    f(i, j) := minimum cost (or steps) required to convert first i characters of word1 to first j characters of word2

    Case 1: word1[i] == word2[j], i.e. the ith the jth character matches.

    f(i, j) = f(i - 1, j - 1)

    Case 2: word1[i] != word2[j], then we must either insert, delete or replace, whichever is cheaper

    f(i, j) = 1 + min { f(i, j - 1), f(i - 1, j), f(i - 1, j - 1) }

    1. f(i, j - 1) represents insert operation
    2. f(i - 1, j) represents delete operation
    3. f(i - 1, j - 1) represents replace operation

    Here, we consider any operation from word1 to word2. It means, when we say insert operation, we insert a new character after word1 that matches the jth character of word2. So, now have to match i characters of word1 to j - 1 characters of word2. Same goes for other 2 operations as well.

    Note that the problem is symmetric. The insert operation in one direction (i.e. from word1 to word2) is same as delete operation in other. So, we could choose any direction.

    Above equations become the recursive definitions for DP.

    Base Case:

    f(0, k) = f(k, 0) = k

    Below is the direct bottom-up translation of this recurrent relation. It is only important to take care of 0-based index with actual code :-

    public class Solution {
        public int minDistance(String word1, String word2) {
            int m = word1.length();
            int n = word2.length();
            
            int[][] cost = new int[m + 1][n + 1];
            for(int i = 0; i <= m; i++)
                cost[i][0] = i;
            for(int i = 1; i <= n; i++)
                cost[0][i] = i;
            
            for(int i = 0; i < m; i++) {
                for(int j = 0; j < n; j++) {
                    if(word1.charAt(i) == word2.charAt(j))
                        cost[i + 1][j + 1] = cost[i][j];
                    else {
                        int a = cost[i][j];
                        int b = cost[i][j + 1];
                        int c = cost[i + 1][j];
                        cost[i + 1][j + 1] = a < b ? (a < c ? a : c) : (b < c ? b : c);
                        cost[i + 1][j + 1]++;
                    }
                }
            }
            return cost[m][n];
        }
    }
    

    Time complexity : If n is the length of word1, m of word2, because of the two indented loops, it is O(nm)


  • 2
    S

    Than you for the excellent explanation, very helpful :)


  • 0
    M

    Thanks a lot~~ Brilliant idea enlightened~


  • 0
    This post is deleted!

  • 15
    K

    quick question, why use the complex form like "a < b ? (a < c ? a : c) : (b < c ? b : c)"? I think using "Math.min(a,Math.min(b,c))" is much easier to observe


  • 0
    W

    @ King_YL. Very true. I should upvote your comment.


  • 0
    F

    @whitehat which one is faster?


  • 0
    Y

    Very clear explanation, thx


  • 0
    M

    @whitehat why "if(word1.charAt(i) == word2.charAt(j))", only discuss cost[i][j], why considering thinking cost[i][j+1]+1 and cost[i+1][j]+1?


  • 1
    public int minDistance(String word1, String word2) {
        int[][] dp = new int[word2.length()+1][word1.length()+1];
        for(int i = 0; i <= word2.length(); i++) {
            for(int j = 0; j <= word1.length(); j++) {
                if(i == 0 && j == 0) dp[i][j] = 0; // no strings given
                else if(i == 0 && j != 0) {
                    dp[i][j] = j; // word2 is empty
                } else if(i != 0 && j == 0) {
                    dp[i][j] = i; // word1 is empty
                } else if(word2.charAt(i-1) != word1.charAt(j-1)) {
                    dp[i][j] = Math.min(dp[i][j-1], Math.min(dp[i-1][j], dp[i-1][j-1])) + 1;
                }else {
                    dp[i][j] = dp[i-1][j-1]; // same characters just carry over previous chars from both
                }
            }
        }
        return dp[word2.length()][word1.length()];
    }

  • 0
    F

    Very clear explanation!


Log in to reply
 

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