Start learning free

LESSON 456 OF 540 · DYNAMIC PROGRAMMING

Edit Distance in TypeScript: O(m · n) Dynamic Programming

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

    TYPESCRIPT · DYNAMIC PROGRAMMING

    Edit Distance in TypeScript, explained

    Problem overview

    The method minDistance receives two strings, word1 and word2, and 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. Both words use lowercase letters and either can be empty, with at most 500 characters each.

    For "horse" and "ros" the answer is 3: replace h with r to get "rorse", delete the second r to get "rose", and delete e to get "ros". Two operations can't do it, because the words differ by two characters in length, 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: a table of prefix answers

    Trying every sequence of operations is far too slow. Solve smaller versions of the problem 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. With m and n the two lengths, 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.

    For every other entry, look at the last characters of the two prefixes, word1[i - 1] and word2[j - 1]. The prefix of length i ends at index i - 1, because the string counts from 0 while the table counts characters.

    • 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 must fix the end, and the entry is 1 plus the smallest of three neighbours:
      • dp[i - 1][j - 1] for a replace: both prefixes lose their last character.
      • dp[i - 1][j] for a delete of word1's last character: only word1's prefix gets shorter.
      • dp[i][j - 1] for an insert of word2's last character at the end: it matches that character, so only word2's prefix gets shorter.

    Filling the table row by row and left to right means the three neighbours are always known before they are needed. For "horse" and "ros" the table is below. Rows go with the prefixes of "horse" from empty to the whole word, and columns with 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 in m and n. Both come up often in the loops.
    2. Create dp as a number[][] with m + 1 rows of n + 1 zeros. Array.from({ length: m + 1 }, ...) calls its function once per row, and each call returns a fresh new Array(n + 1).fill(0).
    3. Fill column 0 with a loop for i from 0 to m, setting dp[i][0] = i: i deletes.
    4. Fill row 0 with a loop for j from 0 to n, setting dp[0][j] = j: j inserts. dp[0][0] is set twice, both times to 0.
    5. Loop over the rest of the table, i from 1 to m and, inside it, j from 1 to n. Row 0 and column 0 are already filled.
    6. Equal last characters: copy the diagonal, dp[i][j] = dp[i - 1][j - 1].
    7. Different last characters: this is the key line. Set dp[i][j] to 1 plus the Math.min of the replace, delete and insert neighbours. Math.min accepts any number of arguments.
    8. Return dp[m][n], the answer for both whole words.

    The solution in TypeScript

    class Solution {
    minDistance(word1: string, word2: string): number {
        const m = word1.length;
        const n = word2.length;
        const dp: number[][] = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
        for (let i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        for (let j = 0; j <= n; j++) {
            dp[0][j] = j;
        }
        for (let i = 1; i <= m; i++) {
            for (let j = 1; j <= n; j++) {
                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], dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
}

    A few TypeScript details:

    • Rows must be separate arrays. new Array(m + 1).fill(new Array(n + 1).fill(0)) would put one row object in every slot, so changing one cell would change it in every row. With Array.from and an arrow function, each row is created by its own call. For example, building two rows the shared way and setting shared[0][1] = 9 gives [[0,9,0],[0,9,0]].
    • Indexing a string. word1[i - 1] gives a one-character string, and === compares two such strings by value.
    • Types are erased. number[][] exists only for the compiler: it is removed when the code is compiled to JavaScript.

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

    Edge cases and common mistakes

    • Empty words. minDistance("", "abc") is 3, minDistance("abc", "") is 3 and minDistance("", "") is 0. All of them come straight from row 0 and column 0, and the loops over the rest never run when either word is empty.
    • Off-by-one on the characters. Entry dp[i][j] is about i characters, so the last one is word1[i - 1]. Using word1[i] compares the wrong characters and reads past the end of the word in the last row.
    • Forgetting the base row and column. With them left as zeros, every turn into or out of an empty prefix looks free.
    • Forgetting the replace. Taking only the insert and delete neighbours counts a replace as two operations. For "ab" and "ba" the answer is 2 either way, but for "a" and "b" the correct answer is 1 and an insert-plus-delete version gives 2.
    • Swapping the inner loops' bounds. The outer loop follows word1 and runs to m, and the inner follows word2 and runs to n. Mixing them up fails when the words have different lengths.

    Testing

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