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

Code

def minDistance(word1: str, word2: str) -> int:
    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

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