Start learning free

LESSON 456 OF 540 · DYNAMIC PROGRAMMING

Edit Distance in Kotlin: O(m · n) Dynamic Programming 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

    KOTLIN · DYNAMIC PROGRAMMING

    Edit Distance in Kotlin, explained

    Problem overview

    minDistance(word1, word2) returns the fewest operations that turn word1 into word2. An operation is one of three, each costing 1: insert a character anywhere, delete a character, or replace a character with another one. Either word can be empty, and both use lowercase letters.

    For "horse" and "ros" the answer is 3: replace h with r (rorse), delete the second r (rose), delete e (ros). For "intention" and "execution" it is 5. For "" and "abc" it is 3, three inserts.

    Approach

    Trying every sequence of operations explodes quickly. Instead, solve smaller versions of the same question and build up. 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].

    The borders

    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 inside

    Fill the table row by row, left to right. Then the entries above, to the left and diagonally up-left of dp[i][j] are already known. Compare the last characters of the two prefixes, word1[i - 1] and word2[j - 1]. The index is i - 1 because the first i characters end at index i - 1: the word counts from 0, the table counts characters.

    • They are equal: no operation is needed for them, so dp[i][j] = dp[i - 1][j - 1]. Spending an operation on either of them is never better.
    • They differ: one operation has to fix the end, and the cost is 1 plus the best of three neighbours:
      • dp[i - 1][j - 1]: replace word1[i - 1] with word2[j - 1], leaving both prefixes one character shorter;
      • dp[i - 1][j]: delete word1[i - 1], so only the prefix of word1 shrinks;
      • dp[i][j - 1]: insert word2[j - 1] at the end, which matches the last character of word2's prefix, so only that prefix shrinks.

    Step by step

    1. Lengths. Store word1.length in m and word2.length in n, since they come up everywhere.
    2. The table. Array(m + 1) { IntArray(n + 1) } makes m + 1 rows. The lambda runs once per row, so each row is its own IntArray of n + 1 zeros.
    3. Column 0. A loop with i over 0..m sets dp[i][0] = i.
    4. Row 0. A loop with j over 0..n sets dp[0][j] = j. The entry dp[0][0] is set twice, both times to 0.
    5. The main loops. i goes over 1..m and j over 1..n, because row 0 and column 0 are done. If a word is empty, the range such as 1..0 is empty and the loop does nothing.
    6. Equal last characters. Copy dp[i - 1][j - 1].
    7. Different last characters. This is the key line: 1 plus minOf of the replace, delete and insert neighbours.
    8. Return dp[m][n].

    The solution in Kotlin

    class Solution {
    fun minDistance(word1: String, word2: String): Int {
        val m = word1.length
        val n = word2.length
        val dp = Array(m + 1) { IntArray(n + 1) }
        for (i in 0..m) {
            dp[i][0] = i
        }
        for (j in 0..n) {
            dp[0][j] = j
        }
        for (i in 1..m) {
            for (j in 1..n) {
                if (word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1]
                } else {
                    dp[i][j] = 1 + minOf(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1])
                }
            }
        }
        return dp[m][n]
    }
}

    Kotlin details worth knowing:

    • The table must be built with a lambda. Array(m + 1) { IntArray(n + 1) } calls the lambda for every row. Writing Array(m + 1) { shared } with one IntArray named shared would put the same array in every row, and a change to one row would show in all of them. With such a table, setting [0][1] to 9 makes [1][1] read 9 too.
    • word1[i - 1] is a Char. Indexing a String gives a Char, and == compares the characters by value.
    • minOf takes three arguments. minOf(a, b, c) exists for Int, so no nested calls are needed.
    • Ranges are inclusive. 0..m includes m. A loop 0 until m would leave the last row unset.

    Tracing an example

    This is the finished table for "horse" and "ros". Rows are prefixes of horse (0 to 5 characters), columns are prefixes of ros (0 to 3):

    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. Look at row 2, column 2: the prefixes ho and ro both end in o, so the entry copies the diagonal entry, dp[1][1] = 1, the cost of turning h into r. In row 1, column 1, the last characters h and r differ, so the entry is 1 plus the smallest of its three neighbours, which are all 0 or 1 there: 1 + 0 = 1.

    Complexity

    Time: there are (m + 1) × (n + 1) entries and each takes constant work: O(m · n). With words of 500 characters that is about 250,000 entries.

    Space: the whole table is O(m · n). Each row only reads itself and the row above, so two rows of n + 1 numbers would be enough for O(n), but keeping the whole table is easier to follow.

    Edge cases and common mistakes

    • Empty words. minDistance("", "abc") is 3 and minDistance("abc", "") is 3. Two empty words give 0.
    • Identical words. The diagonal copies carry 0 all the way, so minDistance("abc", "abc") is 0.
    • Off-by-one in the indexes. Comparing word1[i] with word2[j] reads the wrong characters and, at i == m, fails with an index error. The prefix of length i ends at word1[i - 1].
    • Forgetting the borders. Without them every entry on the edge stays 0, and the answer is too small.
    • Forgetting the 1. In the different-characters case the operation itself costs 1.
    • Swapped letters. minDistance("ab", "ba") is 2: this problem has no swap operation, so it takes two replaces.

    Testing

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