72. Edit Distance - Detailed Explanation

Problem statement

Description:

Given two strings, word1 and word2, return the minimum number of operations required to convert word1 into word2. You have the following three operations permitted on a word:

• Insert a character.
• Delete a character.
• Replace a character.

Examples:

1. Example 1:

   • Input: word1 = "horse", word2 = "ros".
   • Output: 3.
   • Explanation: One way to convert "horse" to "ros" is:
     • "horse" → "rorse" (replace 'h' with 'r').
     • "rorse" → "rose" (remove the first 'r').
     • "rose" → "ros" (remove the 'e').

2. Example 2:

   • Input: word1 = "intention", word2 = "execution".
   • Output: 5.
   • Explanation: One way to convert "intention" to "execution" is:
     • "intention" → "inention" (remove 't').
     • "inention" → "enention" (replace 'i' with 'e').
     • "enention" → "exention" (replace 'n' with 'x').
     • "exention" → "exection" (replace 'n' with 'c').
     • "exection" → "execution" (insert 'u').

Constraints:

• The lengths of the strings can vary, commonly up to 500 characters in many test cases.
• Both strings can be empty.

The minimum number of operations between two strings is called the edit distance, or the Levenshtein distance. This question is an instance of multidimensional dynamic programming. Grokking Dynamic Programming teaches it in the Longest Common Substring chapter. Every cell of a table holds the best answer for one pair of prefixes, and the value of a cell is the cheapest of a small set of earlier cells. Edit Distance is also one of the dynamic programming entries on the Blind 75 list, so it is worth being able to write it from memory.

Hints before the solution

1. Dynamic programming insight: Think about solving the problem for smaller prefixes of the strings. Once you can compute the minimum edit distance for prefixes of word1 and word2, those results build up the answer for the full strings.

2. Base cases are key: Consider what happens when one of the strings is empty. Converting an empty string to a non-empty string, or the reverse, requires inserting or deleting every character.

3. Subproblem relationship: If the last characters of the two strings match, the edit distance for the full strings equals the distance for the prefixes without those last characters. If they differ, consider all three operations and take the cheapest.

Approaches

Approach: dynamic programming (bottom-up)

Idea:

• Define dp[i][j] as the minimum edit distance between the first i characters of word1 and the first j characters of word2.
• Base cases:
  • dp[0][j] = j, since turning an empty string into a string of length j requires j insertions.
  • dp[i][0] = i, since turning a string of length i into an empty string requires i deletions.
• Recurrence relation:
  • If the characters match, meaning word1[i-1] == word2[j-1], then dp[i][j] = dp[i-1][j-1] and the operation count does not rise.
  • Otherwise, consider three moves and take the minimum:
    • Insert: dp[i][j-1] + 1.
    • Delete: dp[i-1][j] + 1.
    • Replace: dp[i-1][j-1] + 1.
  • In one line, that is dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + 1).

Why it works:

• The table builds the answer from solutions to smaller subproblems, and each cell is computed only once.
• Once the dp table is complete, dp[m][n] holds the answer, where m is the length of word1 and n is the length of word2.

Design Gurus teaches this problem in the Edit Distance lesson of Grokking Dynamic Programming, next to the other questions that fill a table over two strings.

Code implementations

Python implementation