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

Solution

The idea is to use dynamic programming: dp(i, j) is answer for question for word1[:i+1], word2[:j+1]. Then if we have on of the words empty, we return length of the other plus one. Then we have 3 options:

  1. dp(i-1, j) + 1if we remove letter with index i from the first word
  2. dp(i, j-1) + 1, if we remove letter with index j from the second word
  3. dp(i-1, j-1) + cost, if we try to replace one letter with another or if letters are equal.

Complexity

Time complexity is $\mathcal{O}(mn)$, space complexity is also. Space complexity can be done in $\mathcal{O}(\max(m,n))$, because we need to keep only one row at a time.

Code

class Solution:
    def minDistance(self, word1, word2):
        @lru_cache(None)
        def dp(i, j):
            if j == -1: return i + 1
            if i == -1: return j + 1
            cost = word1[i] != word2[j]
            return min(dp(i-1,j) + 1, dp(i,j-1) + 1, dp(i-1,j-1) + cost)
        
        return dp(len(word1) - 1, len(word2) - 1)

If you like the solution, you can upvote it on leetcode discussion section: Problem 0072