[LeetCode] 72. Edit Distance

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

Below implementation uses top-down based solution to find the minimum number of operation.

Let distance(i, j) = minimum operations to transform word1[ 0 : i ] to word2 [0 : j ].

There are 3 ways to construct word2[0:j] 

word2[0:j] = distance(i - 1, j) + 1       # delete character word1[i-1]

word2[0:j] = distance(i, j - 1) + 1       # insert character word2[j-1]  

word2[0:j] = distance(i - 1, j - 1)        # if word1[i-1] == word2[j-1]

word2[0:j] = distance(i - 1, j - 1)  + 1 # if word1[i-1] != word2[j-1], replace word1[i-1] with word2[j-1]

distance(i, j) = minimum operation of those 3 ways

from functools import lru_cache

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        
        @lru_cache(maxsize = None)
        def distance(i, j):
            if i == 0:
                return j
            
            if j == 0:
                return i
            
            # delete
            d1 = distance(i-1, j) + 1
            
            # insert
            d2 = distance(i, j-1) + 1
                        
            d3 = distance(i-1, j-1)
            # replace
            if word1[i-1] != word2[j-1]:
                d3 += 1
            
            return min(d1, d2, d3)
        
        return distance(len(word1), len(word2))