Start learning free

LESSON 452 OF 536 · DYNAMIC PROGRAMMING

Edit Distance in Java: Dynamic Programming on a 2D Table

Practice O(m · n) Read the full explanation

You are given two strings word1 and word2. Return the fewest operations that turn word1 into word2.

There are three operations, and each one counts as one:

  • Insert a character anywhere in the word.
  • Delete a character.
  • Replace a character with another one.

 

Example 1:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose (delete 'r')
rose -> ros (delete 'e')
Two operations are not enough: "ros" is two characters shorter, so both would have to be deletes, and deleting letters from "horse" never gives "ros", because its 'o' comes before its 'r'.

Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation:
intention -> inention (delete 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

Example 3:

Input: word1 = "", word2 = "abc"
Output: 3
Explanation: The empty word becomes "abc" by inserting its 3 characters. Each operation adds at most one character, so no fewer will do.

 

Constraints:

  • 0 <= word1.length, word2.length <= 500
  • word1 and word2 are made of lowercase English letters only, a to z. Either of them can be empty.

Note:

Your algorithm should run in O(m · n) time and space, where m is the length of word1 and n the length of word2.



Trying every sequence of operations is far too slow. Solve smaller versions of the problem instead: let dp[i][j] be the fewest operations that turn the first i characters of word1 into the first j characters of word2. The table has (m + 1) × (n + 1) entries, and the answer is dp[m][n].
Row 0 and column 0 stand for an empty prefix. Turning i characters into nothing takes i deletes, so dp[i][0] = i; turning nothing into j characters takes j inserts, so dp[0][j] = j.

Fill the table row by row, so the entries above, to the left and diagonally up-left of dp[i][j] are already known. Look at the last characters of the two prefixes, word1[i - 1] and word2[j - 1]:
  • When they are equal, they need no operation: dp[i][j] = dp[i - 1][j - 1]. Spending an operation on either of them is never better.
  • When they differ, one operation fixes the end of the prefix, and dp[i][j] is 1 plus the smallest of three neighbours:
    • dp[i - 1][j - 1]: replace word1[i - 1] with word2[j - 1]; both prefixes are then one character shorter.
    • dp[i - 1][j]: delete word1[i - 1]; only the prefix of word1 is shorter.
    • dp[i][j - 1]: insert word2[j - 1] at the end; it matches the last character of word2's prefix, which is then one shorter.

The table has (m + 1) × (n + 1) entries, and each one takes a constant amount of work: O(m · n) time and O(m · n) space.
Each row reads only itself and the row above it, so two rows of n + 1 numbers are enough, which brings the space down to O(n). The lesson keeps the whole table, which is easier to follow.
STEP 1 OF 11
    Ctrl + Enter to check

    JAVA · DYNAMIC PROGRAMMING

    Edit Distance in Java, explained

    Problem overview

    The method minDistance(String word1, String word2) returns the fewest operations that turn word1 into word2. There are three operations, each costing one: insert a character anywhere, delete a character, or replace a character with another one.

    For "horse" and "ros" the answer is 3: replace h with r to get "rorse", delete the second r to get "rose", then delete e. For "intention" and "execution" it is 5. For "" and "abc" it is 3: the empty word becomes "abc" by inserting three characters, and each operation adds at most one.

    Approach: solve smaller versions first

    Trying every sequence of operations is far too slow. Instead, solve the problem for every pair of prefixes. Let dp[i][j] be the fewest operations that turn the first i characters of word1 into the first j characters of word2. With m = word1.length() and n = word2.length(), the table has (m + 1) × (n + 1) entries and the answer is dp[m][n].

    Row 0 and column 0 stand for an empty prefix. Turning i characters into nothing takes i deletes, so dp[i][0] = i. Turning nothing into j characters takes j inserts, so dp[0][j] = j.

    The rest of the table is filled row by row, so the entries above, to the left and diagonally up-left of dp[i][j] are known by the time you reach it. Look at the last characters of the two prefixes, word1.charAt(i - 1) and word2.charAt(j - 1):

    • They are equal. They need no operation, so dp[i][j] = dp[i - 1][j - 1]. Spending an operation on either of them is never better.
    • They differ. One operation fixes the end, and dp[i][j] is 1 plus the smallest of three neighbours. dp[i - 1][j - 1] is a replace: both prefixes become one character shorter. dp[i - 1][j] is a delete of word1's last character. dp[i][j - 1] is an insert of word2's last character at the end, which then matches, leaving a shorter word2 prefix.

    The table for "horse" and "ros"

    Printing dp row by row for "horse" (rows) and "ros" (columns) gives:

    [0, 1, 2, 3]
[1, 1, 2, 3]
[2, 2, 1, 2]
[3, 2, 2, 2]
[4, 3, 3, 2]
[5, 4, 4, 3]

    The first row and column are the empty-prefix values. The bottom-right entry, dp[5][3], is 3, the answer. The entry at row 2, column 1 is 2: turning "ho" into "r" takes a replace and a delete. The entry at row 2, column 2 drops to 1, because the o in both words matches and dp[2][2] copies dp[1][1].

    Step by step

    1. Store the lengths of the two words in m and n. They come up often.
    2. Create the table dp as new int[m + 1][n + 1]: one extra row and column for the empty prefixes. It starts filled with zeros.
    3. Fill column 0. Loop i from 0 to m and set dp[i][0] = i, the cost of deleting i characters.
    4. Fill row 0. Loop j from 0 to n and set dp[0][j] = j, the cost of inserting j characters. dp[0][0] is set twice, both times to 0.
    5. Loop over the rest of the table with i from 1 to m, and inside it j from 1 to n. Row 0 and column 0 are already done.
    6. Compare the last characters word1.charAt(i - 1) and word2.charAt(j - 1). The first i characters end at index i - 1: the word counts from 0, the table counts characters. If they are equal, copy dp[i - 1][j - 1].
    7. Otherwise take 1 plus the smallest of the replace, delete and insert neighbours, using one Math.min inside another, since each call compares only two values.
    8. Return dp[m][n].

    The solution in Java

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

    The Java details worth a closer look:

    • Two-dimensional arrays. new int[m + 1][n + 1] creates an array of m + 1 rows, each an int[] of n + 1 zeros. You read an entry with dp[i][j].
    • charAt returns a char. Comparing two char values with == compares the characters themselves, which is correct. Comparing whole String objects with == would compare references, so use equals for that.
    • length() against length. A String has the method length(). An array has the field length, with no parentheses.
    • Nested Math.min. Math.min takes exactly two arguments, so three candidates need two calls.

    Complexity

    Time: O(m · n). The table has (m + 1) × (n + 1) entries, and each takes a constant amount of work.

    Space: O(m · n). The lesson keeps the whole table, which is easier to follow. Each row reads only itself and the row above it, so two rows of n + 1 numbers would be enough and would bring the space down to O(n).

    Edge cases and common mistakes

    • Empty words. minDistance("", "abc") and minDistance("abc", "") both return 3, and minDistance("", "") returns 0. The loops over rows or columns still run for the empty prefix, and the double loop doesn't run at all.
    • Identical words. minDistance("abc", "abc") is 0: every pair of last characters matches, and the diagonal copies 0.
    • Swapped letters are not one operation. minDistance("ab", "ba") is 2, two replaces, because there is no "swap" operation.
    • Off-by-one on indexes. dp[i][j] is about the first i characters, so the matching characters are charAt(i - 1) and charAt(j - 1). Using charAt(i) throws a StringIndexOutOfBoundsException on the last row, where i equals the word's length.
    • Table size. Making the table m by n leaves no room for the empty prefixes.
    • Forgetting the base row and column. The inner loops would read zeros where the costs i and j belong, and every answer would come out too small.

    Testing

    • "horse" to "ros" gives 3.
    • "intention" to "execution" gives 5.
    • "kitten" to "sitting" gives 3.
    • "ab" to "ba" gives 2.
    • "" to "abc" gives 3.
    • "abc" to "abc" gives 0.
    Keep going with Java500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free