Start learning free

LESSON 456 OF 540 · DYNAMIC PROGRAMMING

Edit Distance in Scala: Dynamic Programming over Prefixes

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

    SCALA · DYNAMIC PROGRAMMING

    Edit Distance in Scala, explained

    Problem overview

    The method minDistance receives two strings, word1 and word2, and returns the fewest operations that turn word1 into word2. The operations are inserting a character anywhere, deleting a character, and replacing a character with another one. Each costs 1. Both words are lowercase letters and either may be empty.

    For "horse" and "ros" the answer is 3: replace h with r to get rorse, delete the second r to get rose, delete e to get ros. Two operations cannot work, because "ros" is two characters shorter, so both would have to be deletes, and deleting letters from "horse" never gives "ros". For "" and "abc" the answer is 3, three inserts.

    Approach: solve every pair of prefixes

    Trying every sequence of operations is far too slow. The method solves 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, where m and n are the word lengths, 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.

    Every other entry is filled from three neighbours that are already known, by looking at the last characters of the two prefixes, word1(i - 1) and word2(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 the entry is 1 plus the smallest of three neighbours. dp(i - 1)(j - 1) is a replace: both prefixes lose their last character. dp(i - 1)(j) is a delete of word1's character. dp(i)(j - 1) is an insert of word2's character at the end, which matches the last character of word2's prefix.

    This is the full table for "horse" and "ros". Rows are the prefixes of horse (including the empty one), columns the prefixes of ros:

    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 bottom-right entry, 3, is the answer.

    Step by step

    1. Store the lengths of the words in m and n, one val each. They come up in the table size and in every loop.
    2. Create the table dp with Array.ofDim[Int](m + 1, n + 1), which makes m + 1 rows of n + 1 zeros. The extra row and column are the empty prefixes.
    3. Fill column 0 with a loop over i <- 0 to m, setting dp(i)(0) to i. Both ends are included, because every row has an entry in column 0.
    4. Fill row 0 with a loop over j <- 0 to n, setting dp(0)(j) to j. The corner dp(0)(0) is set twice, both times to 0.
    5. Loop over the rest of the table row by row with i <- 1 to m and, inside it, j <- 1 to n. Row 0 and column 0 are already done, so both loops start at 1. In this order the entries above, to the left and diagonally up-left are filled before they are needed.
    6. Handle equal characters. Compare word1(i - 1) with word2(j - 1). A prefix of length i ends at index i - 1, because a word counts from 0 and the table counts characters. If they are equal, copy dp(i - 1)(j - 1).
    7. Handle different characters in the else. Set the entry to 1 plus the minimum of the replace, delete and insert neighbours. Two math.min calls are nested, since each compares just two values.
    8. Return dp(m)(n) as the last expression of the method.

    The solution in Scala

    class Solution {
    def minDistance(word1: String, word2: String): Int = {
        val m = word1.length
        val n = word2.length
        val dp = Array.ofDim[Int](m + 1, n + 1)
        for (i <- 0 to m) {
            dp(i)(0) = i
        }
        for (j <- 0 to n) {
            dp(0)(j) = j
        }
        for (i <- 1 to m) {
            for (j <- 1 to n) {
                if (word1(i - 1) == word2(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)))
                }
            }
        }
        dp(m)(n)
    }
}

    The Scala details worth a closer look:

    • Array.ofDim[Int](m + 1, n + 1) creates an array of arrays, with every element 0. For Array.ofDim[Int](2, 3) the rows print as 0,0,0 | 0,0,0. Its type is Array[Array[Int]].
    • One pair of parentheses per dimension. An element is dp(i)(j): dp(i) is a row, and the second pair picks the column. Assignment looks the same, dp(i)(0) = i.
    • Strings are indexed like arrays. word1(i - 1) is the Char at that index, and == compares two Chars by value.
    • Empty words are safe. If word1 is empty, m is 0, and 1 to m is an empty range, so the main loops do nothing and dp(0)(n) is n. The same holds for an empty word2.
    • math.min takes two arguments. To find the smallest of three values, nest two calls, as the lesson does.
    • to versus until. 0 to m includes m, which the table needs, since it has m + 1 rows. 0 until m would stop one row short.

    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. Each row reads only itself and the row above it, so two rows of n + 1 numbers would be enough and would lower the space to O(n). The full table is easier to follow.

    Edge cases and common mistakes

    • An empty word. minDistance("", "abc") is 3 and minDistance("abc", "") is also 3. Two empty words give 0.
    • Equal words. minDistance("same", "same") is 0, because the diagonal copies zeros all the way down.
    • Swapped letters. minDistance("ab", "ba") is 2: there is no swap operation, so two replaces are needed. Its table is: 
      0 1 2
1 1 1
2 1 2
    • One word is a prefix of the other. minDistance("abc", "ab") is 1, a single delete.
    • Using i instead of i - 1 to read the characters. The table has one more row and column than the words have characters, so word1(i) reads the wrong letter, and for i = m it is out of range.
    • Forgetting the + 1 for the operation. Without it, the entry would just copy the cheapest neighbour, and differences between the words would cost nothing.
    • Skipping the first row and column. Without the base cases, every entry depends on zeros that should have been i and j, and all answers come out too small.

    Testing

    • "horse" and "ros" give 3.
    • "intention" and "execution" give 5.
    • "" and "abc" give 3.
    • "abc" and "" give 3.
    • "a" and "b" give 1.
    • Two strings of 500 letters each, a repeated against b repeated, give 500.
    Keep going with Scala500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free