Edit Distance

Problem Statement

You are given two strings word1 and word2, each consisting of lowercase English letters.

You are allowed to perform three operations on word1 an unlimited number of times:

  • Insert a character at any position
  • Delete a character at any position
  • Replace a character at any position

Return the minimum number of operations to make word1 equal word2.

Example 1:

Input: word1 = "monkeys", word2 = "money"


Output: 2

Explanation: monkeys -> monkey (remove s) monkey -> money (remove k)

Example 2:

Input: word1 = "pithoncdee", word2 = "pythoncode"


Output: 3

Explanation: pithoncdee -> pythoncdee (replace i with y) pythoncdee -> pythoncde (remove last e) pythoncde -> pythoncode (insert o)

Constraints:

  • 0 <= word1.length, word2.length <= 100
  • word1 and word2 consist of lowercase English letters.

You should aim for a solution with O(m * n) time and O(min(m, n)) space, where m and n are the lengths of word1 and word2 respectively.

Hint 1

Consider using dynamic programming to solve this problem.

Hint 2

Define dp[i][j] as the minimum number of operations to convert word1[0...i-1] to word2[0...j-1].

Hint 3

If word1[i-1] == word2[j-1], then dp[i][j] = dp[i-1][j-1].

Hint 4

Otherwise, dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1, representing deletion, insertion, and replacement, respectively.

Solution

Recursion

def min_distance_recursive(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)


    def dfs(i, j):
        if i == m:
            return n - j
        if j == n:
            return m - i
        if word1[i] == word2[j]:
            return dfs(i + 1, j + 1)
        res = min(dfs(i + 1, j), dfs(i, j + 1))
        res = min(res, dfs(i + 1, j + 1))
        return res + 1


    return dfs(0, 0)

Time complexity: O(3 ^ {m + n}) Space complexity: O(m + n)