LeetCode 72: Edit Distance Solution in Python Explained

Problem Statement

LeetCode 72, Edit Distance, is a hard-level problem where you’re given two strings word1 and word2. Your task is to compute the minimum number of operations required to convert word1 into word2, using only three operations: insert a character, delete a character, or replace a character. Return this minimum edit distance as an integer.

Constraints

  • 0 <= word1.length, word2.length <= 500: String lengths are between 0 and 500.
  • word1 and word2 consist of lowercase English letters.

Example

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
<ul>
<li>Replace 'h' with 'r': "rorse"</li>
<li>Delete 'r': "rose"</li>
<li>Delete 'e': "ros"</li>
</ul>
Total = 3 operations.

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: 
<ul>
<li>Insert 'e': "eintention"</li>
<li>Replace 'i' with 'x': "exntention"</li>
<li>Delete 'n': "extention"</li>
<li>Replace 't' with 'c': "execution"</li>
<li>Delete 'n': "execution"</li>
</ul>
Total = 5 operations.

Input: word1 = "", word2 = "abc"
Output: 3
Explanation: Insert 'a', 'b', 'c' -> 3 operations.

Understanding the Problem

How do you solve LeetCode 72: Edit Distance in Python? For word1 = "horse" and word2 = "ros", find the minimum operations to transform "horse" into "ros"—here, it’s 3 (replace, delete, delete). This is a classic dynamic programming problem, also known as the Levenshtein distance. We’ll explore two approaches: a Dynamic Programming Solution (optimal and primary) and an Alternative with Space-Optimized DP (more memory-efficient). The DP method runs in O(m * n) time with O(m * n) space, where (m) and (n) are the string lengths.

Solution 1: Dynamic Programming Approach (Primary)

Explanation

Use a 2D DP table where dp[i][j] represents the minimum edit distance between the first (i) characters of word1 and the first (j) characters of `word2). For each cell:

  • If characters match, dp[i][j] = dp[i-1][j-1].
  • If they differ, take the minimum of:
    • Insert: dp[i][j-1] + 1 (add to word1).
    • Delete: dp[i-1][j] + 1 (remove from word1).
    • Replace: dp[i-1][j-1] + 1 (change in word1).

Initialize the first row and column with incremental costs (insertions or deletions), then fill the table.

Here’s a flow for "horse" to "ros":

DP table:
    r o s
  0 1 2 3
h 1 1 2 3
o 2 2 1 2
r 3 2 2 2
s 4 3 2 2
e 5 4 3 3
Result: dp[5][3] = 3
  1. Initialize DP Table.
  • Size \((m+1) \times (n+1)\), set first row and column.
  1. Fill Table.
  • Compare characters, compute min operations.
  1. Return Result.
  • Value at dp[m][n].

Step-by-Step Example

Example 1: word1 = "horse", word2 = "ros"

We need 3.

  • Goal: Minimum edit distance from "horse" to "ros".
  • Result for Reference: 3.
  • Start: m = 5, n = 3, dp = [[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]].
  • Step 1: Initialize first row and column.
    • dp[0] = [0,1,2,3] (insert r,o,s).
    • dp[i][0] = [0,1,2,3,4,5] (delete h,o,r,s,e).
  • Step 2: Fill table.
    • dp[1][1]: 'h' vs 'r', min(insert=2, delete=1, replace=1) = 1, dp[1][1] = 1.
    • dp[1][2]: 'h' vs 'o', min(3,2,2) = 2, dp[1][2] = 2.
    • dp[1][3]: 'h' vs 's', min(4,3,3) = 3, dp[1][3] = 3.
    • dp[2][1]: 'o' vs 'r', min(2,2,2) = 2, dp[2][1] = 2.
    • dp[2][2]: 'o' vs 'o', dp[1][1] = 1, dp[2][2] = 1.
    • dp[2][3]: 'o' vs 's', min(2,3,2) = 2, dp[2][3] = 2.
    • dp[3][1]: 'r' vs 'r', dp[2][0] = 2, dp[3][1] = 2.
    • Continue filling: dp = [[0,1,2,3],[1,1,2,3],[2,2,1,2],[3,2,2,2],[4,3,2,2],[5,4,3,3]].
  • Finish: Return dp[5][3] = 3.

Example 2: word1 = "intention", word2 = "execution"

We need 5.

  • Start: m = 9, n = 9, dp size = 10x10.
  • Step 1: Initialize: dp[0] = [0,1,2,3,4,5,6,7,8,9], dp[i][0] = [0,1,2,3,4,5,6,7,8,9].
  • Step 2: Fill key cells (abridged):
    • dp[1][1]: 'i' vs 'e', min(2,2,1) = 1.
    • dp[9][9]: Final cell computes to 5 after all steps.
  • Finish: Return dp[9][9] = 5.

How the Code Works (Dynamic Programming)

Here’s the Python code with line-by-line explanation:

def minDistance(word1: str, word2: str) -> int:
    # Line 1: Get lengths
    m, n = len(word1), len(word2)

    # Line 2: Initialize DP table
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i  # Delete cost
    for j in range(n + 1):
        dp[0][j] = j  # Insert cost

    # Line 3: Fill DP table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1]  # No operation needed
            else:
                dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1

    # Line 4: Return minimum edit distance
    return dp[m][n]

Alternative: Space-Optimized DP Approach

Explanation

Optimize space by using a 1D DP array, updating it row by row. Each dp[j] represents the minimum distance to convert the prefix of word1 to the prefix of word2 up to (j), needing only the current and previous row values, reducing space to O(n).

  1. Initialize 1D DP.
  • Size \(n+1\), set first row costs.
  1. Process Rows.
  • Update array, tracking previous value.
  1. Return Result.
  • Last element of array.

Step-by-Step Example (Alternative)

For "horse" to "ros":

  • Start: dp = [0,1,2,3].
  • Step 1: Row 1 ('h').
    • dp[1] = min(2,1) + 1 = 1, dp = [1,1,2,3].
  • Step 2: Row 2 ('o').
    • dp[1] = min(2,2) = 2, dp[2] = min(2,1) + 1 = 1, dp = [2,2,1,2].
  • Step 3: Row 3 ('r').
    • dp[1] = min(3,2) = 2, dp[2] = min(2,2) + 1 = 2, dp = [3,2,2,2].
  • Step 4: Row 4 ('s').
    • dp[3] = min(2,2) = 2, dp = [4,3,2,2].
  • Step 5: Row 5 ('e').
    • dp[3] = min(2,3) + 1 = 3, dp = [5,4,3,3].
  • Finish: Return dp[3] = 3.

How the Code Works (Space-Optimized DP)

def minDistanceOpt(word1: str, word2: str) -> int:
    # Line 1: Get lengths and initialize DP array
    m, n = len(word1), len(word2)
    dp = list(range(n + 1))

    # Line 2: Process each row
    for i in range(1, m + 1):
        prev = i  # Previous row’s dp[0]
        for j in range(1, n + 1):
            temp = dp[j]
            if word1[i-1] == word2[j-1]:
                dp[j] = prev
            else:
                dp[j] = min(dp[j], dp[j-1], prev) + 1
            prev = temp

    # Line 3: Return minimum edit distance
    return dp[n]

Complexity

  • Dynamic Programming:
    • Time: O(m * n) – Fill \(m \times n\) table.
    • Space: O(m * n) – Store DP table.
  • Space-Optimized DP:
    • Time: O(m * n) – Process each cell.
    • Space: O(n) – 1D array.

Efficiency Notes

Space-Optimized DP is O(m * n) time and O(n) space, more efficient than full DP’s O(m * n) space, making it a strong choice for LeetCode 72. Both are O(m * n) time, fitting the constraint of string lengths up to 500.

Key Insights

Tips to master LeetCode 72:

  • DP Recurrence: Min of insert, delete, replace.
  • Base Cases: First row/column as incremental costs.
  • Space Saving: Use 1D array with prev tracking.

Additional Example

For word1 = "cat", word2 = "cut":

  • Goal: 1.
  • DP: [[0,1,2,3],[1,1,2,3],[2,2,1,2],[3,3,2,1]], return 1.
  • Result: 1.

Edge Cases

  • Empty Strings: "" to "abc" – Return 3.
  • Same Strings: "abc" to "abc" – Return 0.
  • Single Char: "a" to "b" – Return 1.

Final Thoughts

The Dynamic Programming solution is a robust pick for LeetCode 72 in Python—clear and comprehensive, with the Space-Optimized version enhancing efficiency. For a related challenge, try LeetCode 71: Simplify Path to switch to string parsing! Ready to edit? Solve LeetCode 72 on LeetCode now and test it with "horse" to "ros" or "intention" to "execution" to master edit distance. Dive in and transform those strings!