mq061.编辑距离

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        l1, l2 = len(word1), len(word2)
        dp = [[0]*(l2+1) for x in range(l1+1)]
        for x in range(l1+1):
            dp[x][0] = x
        for y in range(l2+1):
            dp[0][y] = y
        for x in range(1, l1+1):
            for y in range(1, l2+1):
                left = dp[x][y-1] + 1
                up = dp[x-1][y] + 1
                left_up = dp[x-1][y-1]
                if word1[x-1] != word2[y-1]:
                    left_up += 1
                dp[x][y] = min(left, up, left_up)
        return dp[l1][l2]