Leetcode: Edit Distance

This question is asked at Amazon, and is a very highly voted dynamic programming problem. It is so common, it is used in algorithm textbooks. Given two strings word1 and word2, I want to return the minimum number of operations required to convert word1 to word2. I can either insert a character, delete a character, or replace a character.

Here are some examples: 

Example 1:

Input: word1 = "horse", word2 = "ros"

Output: 3

Explanation: 

horse -> rorse (replace 'h' with 'r')

rorse -> rose (remove 'r')

rose -> ros (remove 'e')

Example 2:

Input: word1 = "intention", word2 = "execution"

Output: 5

Explanation: 

intention -> inention (remove 't')

inention -> enention (replace 'i' with 'e')

enention -> exention (replace 'n' with 'x')

exention -> exection (replace 'n' with 'c')

exection -> execution (insert 'u')

 

Constraints:

0 <= word1.length, word2.length <= 500

word1 and word2 consist of lowercase English letters.

Now here is the explanation on how to solve the problem. f(i,j) is the minimum cost or steps required to convert the first i characters of word1 to the first j characters of word2. 

There's many cases. If the word matches, then we just move on, otherwise if the word doesn't match, we append the minimum of 3 cases. So

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

f(i,j) = 1 + min ((f(i, j - 1), f(i - 1, j), f(i - 1, j - 1)) which is the case 2, where (i, j - 1) represents the insert operation, (i - 1, j) represents delete and (i - 1, j - 1) represents replace. The base case is f(0, k) or f(k, 0) = k, because they require k insertions. Since this is a dynamic programming table, the time complexity is O(mn). Such is the final code: 

public int minDistance(String word1, String word2) {

    //word lengths

   int m = word1.length();

   int n = word2.length();

   int[][] cost = new int[m + 1][n + 1];

    //for the base case, set the insertions of a null word as lenght of other word.

   for(int i = 0; i <= m; i++) {

        const[i][0] = i;

    }

    for(int j = 0; j <= n; j++) {

        const[0][j] = j;

    }

    //go over dp array

    for(int i = 0; i < m; i++) {

        for(int j = 0; j < n; j++) {

            //move on if words are equal no need for change

            if(word1.charAt(i) == word2.charAt(j)) {

                cost[i + 1][j + 1] = cost[i][j]

            } else {

                //add remove and replace word

                int add = cost[i + 1][j];

                int remove = cost[i][j + 1];

                int rep = cost[i][j];

                //account for those, perform the dp step 

                cost[i + 1][j + 1] = Math.min(Math.min(add, remove), rep) + 1;

            }

        }

        //return the dp value.

        return cost[m][n]; 

    }

}