Edit Distance

Dynamic Programming

HardLeetCode #72

35 min

Problem Statement

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

Insert a character
Delete a character
Replace a character

Example

Example 1:

Word 1:horse

Word 2:ros

Edit Distance:3

1. Replace 'h' with 'r' ("rorse")

2. Delete 'r' ("rose")

3. Delete 'e' ("ros")

Solution

This is a classic 2D dynamic programming problem. We'll create a DP grid, dp, of size (m+1) x (n+1), where m and n are the lengths of the two words. dp[i][j] will represent the minimum number of operations to convert the first i characters of word1 to the first j characters of word2.

The recurrence relation is as follows: If word1[i-1] == word2[j-1], then dp[i][j] = dp[i-1][j-1]. Otherwise, dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]), which correspond to deletion, insertion, and replacement.

Algorithm Steps (DP)

Create a DP grid of size (m+1) x (n+1).
Initialize the first row and column based on the cost of deletions/insertions.
Iterate through the grid from (1, 1) to (m, n).
If word1[i-1] == word2[j-1], dp[i][j] = dp[i-1][j-1].
Otherwise, dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]).
The final answer is dp[m][n].

Recurrence Relation

dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

Step: 1 / 17

Edit Distance Solution


def minDistance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j

    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]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])

    return dp[m][n]