Edit Distance

Problem

https://leetcode.com/problems/edit-distance/

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 1:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation:
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:

• 0 <= word1.length, word2.length <= 500

• word1 and word2 consist of lowercase English letters.

Pattern

String, Dynamic Programming

Approaches

Dynamic Programming

Explanation

Let edit_dist[i][j] be the minimum number of operations required to convert word1[:i] into word2[:j]. There are 3 operations we can try which each correspond to previous edit distances.

1. Delete from word1 -> edit_dist[i - 1][j]

2. Insert into word1 -> edit_dist[i][j - 1]

3. Replace the character -> edit_dist[i - 1][j - 1]

We want to pick the operation that minimizes edit_dist[i][j] the most, which is the operation with the corresponding smallest edit distance.

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

If word1[i - 1] == word2[j - 1], then edit_dist[i][j] = edit_dist[i - 1][j - 1] as no change is needed.

In the base case where i = 0 or j = 0, we need to insert j or i characters to transform an empty string into words2[:j] or delete i characters to transform words1[:i] into an empty string.

Code

def minDistance(word1: str, word2: str) -> int:
    """Calculate the minimum edit distance (the number of operations required
    to transform ``word1`` into ``word2``.
    """
    M = len(word1)
    N = len(word2)

    edit_dist = [[0 for _ in range(N + 1)] for _ in range(M + 1)]

    for i in range(M + 1):
        edit_dist[i][0] = i

    for j in range(N + 1):
        edit_dist[0][j] = j

    for i in range(1, M + 1):
        for j in range(1, N + 1):
            if word1[i - 1] == word2[j - 1]:
                edit_dist[i][j] = edit_dist[i - 1][j - 1]
            else:
                edit_dist[i][j] = 1 + min(
                    edit_dist[i][j - 1],
                    edit_dist[i - 1][j],
                    edit_dist[i - 1][j - 1],
                )

    return edit_dist[-1][-1]

Test

>>> from edit_distance__dynamic_programming import minDistance
>>> minDistance("horse", "ros")
3
>>> minDistance("intention", "execution")
5

Complexity

Measure	Complexity	Notes
Time	\(O(mn)\)	loop through \(i = 0, \dots, m\) and \(j = 0, \dots, m\)
Auxiliary Space	\(O(mn)\)	2D edit_dist array

edit_distance__dynamic_programming.minDistance(word1: str, word2: str) → int

Calculate the minimum edit distance (the number of operations required to transform word1 into word2.