0583：两个字符串的删除操作（★）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def minDistance(self, word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    dp = list(range(n+1))
    for char in word1:
        prev = dp[:]
        dp[0] += 1
        for j in range(1, n+1):
            if word2[j-1]==char:
                dp[j] = prev[j-1]
            else:
                dp[j] = 1+min(prev[j], dp[j-1])
    return dp[-1]