Leetcode刷题记录——72. 编辑距离

设word1的长度是m
word2的长度是n
dp是一个m+1行 n+1列的矩阵
dp[0][0] = 0
其中 第0行第i个元素表示 从一个空字符串变到word2[:i] 最少需要几步 很明显需要i步
其中 第0行第j个元素表示 从一个空字符串变到word1[:i] 最少需要几步 很明显需要i步
而dp[i][j] i,j均大于1 表示 从word1[:i]变到word2[:j]最少需要几步
看几种情况
假设我们知道从word1[:i-1]变到word2[:j]需要x步 则从word1[:i]变到word2[:j]需要
x（word1[:i-1]先变到word2[:j]） + 1 （再填上一个word1[i]）
假设我们知道从word1[:i]变到word2[:j-1]需要y步 则从word1[:i]变到word2[:j]需要
y + 1步 同理
假设我们知道从word1[:i-1]变到word2[:j-1]需要z步 则从word1[:i]变到word2[:j]需要
这时需要讨论一下
如果word1[i] == word[j]则我们只需要调整word1[:i-1]变到word2[:j-1]即可 不需要管最后的相等那位 此时是z步
若不相等 需要替换一次 z+1步

因此 在word1[i] == word[j]的情况下 需要min(z,x+1,y+1)
若不相等 则为min(z+1,x+1,y+1)

返回dp[-1][-1]

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        #word1,word2 = word2,word1
        m = len(word1)
        n = len(word2)
        dp = []#m行 n列
        if m == 0 and n == 0:
            return 0
        elif m == 0:
            return n
        elif n == 0:
            return m
        for i in range(m+1):
            dp.append([0 for _ in range(n+1)])
        for i in range(n+1):#先填充第0行
            dp[0][i] = i
        for i in range(1,m+1):
            dp[i][0] = i
        
        for x in range(1,m+1):
            for y in range(1,n+1):
                if word1[x-1] == word2[y-1]:
                    dp[x][y] = min(dp[x-1][y] +1,dp[x][y-1] + 1,dp[x-1][y-1]) 
                else:
                    dp[x][y] = min(dp[x-1][y],dp[x][y-1],dp[x-1][y-1]) + 1

        return dp[-1][-1]

本文地址：https://blog.csdn.net/weixin_41545780/article/details/107578426