欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-04-18 09:24:52
设word1的长度是mword2的长度是ndp是一个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]变到wor....

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