Start learning free

LESSON 455 OF 539 · DYNAMIC PROGRAMMING

Edit Distance in C#: 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

    C# · DYNAMIC PROGRAMMING

    Edit Distance in C#, explained

    Problem overview

    The method MinDistance receives two strings, word1 and word2, and returns the fewest operations that turn word1 into word2. Three operations exist and each costs one: insert a character anywhere, delete a character, or replace a character with another one. Either word may be empty, and both have at most 500 lowercase letters.

    For "horse" and "ros" the answer is 3: replace h with r, delete the second r, delete e. For "intention" and "execution" it is 5. For "" and "abc" it is 3, three inserts, because each operation adds at most one character.

    The lesson asks for O(m · n) time and space, where m and n are the two lengths.

    Approach: solve every pair of prefixes

    Trying every sequence of operations explodes quickly. The way out is to solve smaller versions of the same question. 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, and they are known without any search. 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 comes from 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 dp[i, j] 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 last character. dp[i, j - 1] is an insert of word2's last character at the end, which then matches, leaving a shorter prefix of word2.

    Filling the table row by row, left to right, guarantees that the three neighbours above, to the left and diagonally up-left are ready when an entry is computed.

    The table for "horse" and "ros"

    Here is the whole table for word1 = "horse" (rows 0 to 5) and word2 = "ros" (columns 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, dp[5, 3], is 3, the answer. Two entries show both cases. In dp[3, 2] ("hor" against "ro") the last characters r and o differ, and the smallest neighbour is dp[2, 2] = 1, so the entry is 1 + 1 = 2. In dp[4, 3] ("hors" against "ros") the last characters are both s, so the entry copies dp[3, 2], which is 2.

    Step by step

    1. Store the lengths word1.Length and word2.Length in m and n. They are used in the table size and in every loop bound.
    2. Create dp as an int[,] with m + 1 rows and n + 1 columns. The extra row and column hold the empty prefixes. A new array starts filled with zeros.
    3. Loop i from 0 to m to fill column 0, and set dp[i, 0] to i: i deletes empty the prefix.
    4. Loop j from 0 to n to fill row 0, and set dp[0, j] to j: j inserts build the prefix. The corner dp[0, 0] is set twice, both times to 0.
    5. Loop over the remaining rows, i from 1 to m, and over the columns, j from 1 to n. Row 0 and column 0 are filled already.
    6. Compare word1[i - 1] with word2[j - 1]. The first i characters end at index i - 1, because the strings count from 0 and the table counts characters. When equal, copy dp[i - 1, j - 1].
    7. Otherwise take 1 plus the smallest of the three neighbours, using one Math.Min inside another, since each call compares only two values.
    8. Return dp[m, n]. It covers all of both words.

    The solution in C#

    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[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]));
                }
            }
        }
        return dp[m, n];
    }
}

    The C# details worth knowing:

    • Rectangular arrays. int[,] is a single block indexed with one pair of brackets, dp[i, j]. Code written as dp[i][j] belongs to jagged arrays (int[][]) and won't compile here. For a 3 by 4 table, GetLength(0) is 3, GetLength(1) is 4 and Length is 12, the total number of cells.
    • Strings are indexable. word1[i - 1] is a char, and == on two char values compares them directly. A string can't be changed in place, but this solution only reads characters.
    • Length is a property. Write word1.Length without parentheses. The empty string "" has length 0, so the table is 1 by n + 1 and the loops handle it with no special case.
    • Bounds are checked. Reading word1[i] when i equals the length throws an IndexOutOfRangeException instead of reading garbage. This is the usual result of forgetting the - 1.
    • Math.Min takes two arguments. To take the minimum of three values, nest the calls, as the lesson does.

    Complexity

    Time: O(m · n). The table has (m + 1) × (n + 1) entries and each one takes constant work, a comparison and at most three reads.

    Space: O(m · n). The full table is kept, which makes the solution easy to follow. Each row reads only itself and the row above, so two rows of n + 1 numbers would be enough and would bring the space down to O(n). With words of 500 characters the full table has about 251,000 integers, which is small.

    Edge cases and common mistakes

    • Empty words. ("", "abc") returns 3, ("abc", "") returns 3 and ("", "") returns 0, all straight from the first row and column.
    • Equal words. ("abc", "abc") returns 0: every comparison copies the diagonal, which stays 0.
    • Swapped neighbours. ("ab", "ba") returns 2. There is no swap operation, so two replaces are needed.
    • One replace. ("a", "b") returns 1.
    • Off by one on the characters. The table index i corresponds to character i - 1 of the word. Using word1[i] is wrong and throws at the last row.
    • Forgetting the base row and column. With them left at zero, ("", "abc") would give 0 instead of 3.
    • Missing a neighbour in the minimum. Using only the diagonal ignores inserts and deletes, and words of different lengths come out wrong.
    • Forgetting the 1. The operation itself has to be counted, so the minimum alone is not the answer for differing characters.

    Testing

    • "horse" and "ros" gives 3.
    • "intention" and "execution" gives 5.
    • "" and "abc" gives 3.
    • "abc" and "" gives 3.
    • "ab" and "ba" gives 2.
    • "a" and "b" gives 1.
    • Two words of 500 different letters ('a' repeated against 'b' repeated) give 500.
    Keep going with C#500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free