72.EditDistance.py

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:

        def dfs(i: int, j: int) -> int:
            if i == len(word1):
                return len(word2) - j

            if j == len(word2):
                return len(word1) - i

            if memo[i][j] is not None:
                return memo[i][j]

            ans = 0
            if word1[i] == word2[j]:
                ans = dfs(i + 1, j + 1)
            else: 
                ans = 1 + min(dfs(i + 1, j + 1), min(dfs(i + 1, j), dfs(i , j + 1)))

            memo[i][j] = ans

            return ans

        memo = [[None] * len(word2) for _ in range(len(word1))]

        return dfs(0, 0)