# -*- coding: utf-8 -*-
import math
def minDistance(word1, word2):
    '''
    Input: word1 = "horse", word2 = "ros"
    Output: 3
    Explanation:
    horse -> rorse (replace 'h' with 'r')
    rorse -> rose (remove 'r')
    rose -> ros (remove 'e')
    '''

    n = len(word1)
    m = len(word2)
    dp = [[math.inf for i in range(m+1)] for j in range(n+1)]

    for i in range(m+1):
        dp[0][i] = i

    for i in range(n+1):
        dp[i][0] = i

    for i in range(1, n+1):
        for j in range(1, m+1):
            if word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:

                dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

    return dp[n][m]

print(minDistance('horse', 'ros'))