Solutions

# Top down or bottom up DP. 3 choices: insert, delete, replace.
# dp

# Top-down DP - O(m*n) time, O(m*n) space
def minDistance(word1: str, word2: str) -> int:
    dp = {}

    # dfs(i,j): min number of operations to get from word1[i:] to word2[j:]
    def dfs(i: int, j: int) -> int:
        if i == len(word1):
            # If i goes out of bounds, we insert remaining characters of word2
            return len(word2[j:])
        if j == len(word2):
            # If j goes out of bounds, we delete remaining characters of word1
            return len(word1[i:])
        if (i,j) in dp:
            return dp[(i,j)]

        res = 99999
        if word1[i] == word2[j]:
            res= dfs(i+1, j+1)
        else:
            insert = 1 + dfs(i, j+1)
            delete = 1 + dfs(i+1, j)
            replace = 1 + dfs(i+1, j+1)
            res = min(delete, replace, insert)
        dp[(i,j)] = res
        return res

    return dfs(0, 0)

# Bottom-up DP - O(m*n) time, O(m*n) space
def minDistance(word1: str, word2: str) -> int:

    n = len(word1)
    m = len(word2)
    cache = [[99999] * (m+1) for _ in range(n+1)]
    # cache[i][j]: min number of operations to get from word1[i:] to word2[j:]

    # Base cases:
    # "abd.." -> "" (empty string) 
    for i in range(m+1):
        cache[n][i] = m - i
    # "" (empty string) -> "abd.."
    for i in range(n+1):
        cache[i][m] = n - i

    for r in range(n-1, -1, -1):
        for c in range(m-1, -1, -1):
            if word1[r] == word2[c]:
                cache[r][c] = cache[r+1][c+1]
            else:
                cache[r][c] = 1+ min(cache[r+1][c],
                                        cache[r][c+1],
                                        cache[r+1][c+1])
    return cache[0][0]