[动态规划]Leetcode72.编辑距离

如果读者对于动态规划思路解法还不是很了解，可以先点击链接查阅我之前的一篇博文《算法之【动态规划】详解》，很详细的介绍了动态规划求解思路及方法，有利于你更好的学习动态规划。

题目描述

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

示例1

输入：word1 = “horse”, word2 = “ros”

输出：3

解释：

horse -> rorse (将 ‘h’ 替换为 ‘r’)

rorse -> rose (删除 ‘r’)

rose -> ros (删除 ‘e’)

DP定义及状态方程

对于两个字符串类型的问题，使用常用定义套路，定义dp[i][j]表示word1[1...i]与word2[1...j]的最小编辑距离，则

1. 当word1[i-1]==word2[j-1]时，有dp[i][j]=dp[i-1][j-1]

2. 当word1[i-1]！=word2[j-1]时，可对dp[i][j]进行插入、删除、替换操作，插入时dp[i][j]=dp[i][j-1] +1;删除时dp[i][j]=dp[i-1][j] +1;替换时dp[i][j]=dp[i-1][j-1] +1;

因此dp[i][j]的最小值为这三个操作对应的最小值，即dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1。

此题目的最终答案即为dp数组最后一个值：dp[-1][-1]

初始边界条件

1. dp[0][j]对应的编辑距离即为j，因为从空字符串变为word2[1..j]字符串，至少需要j次插入字符操作；

2. dp[i][0]对应的编辑距离即为i，因为从word1[1..i]字符串变为空符操作，至少需要i次删除字符操作；

最终代码

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m = len(word1)
        n = len(word2)
        dp = [[0]*(n+1) for _ in range(m+1)]
        for i in range(m+1):
            dp[i][0] = i
        for j in range(n+1):
            dp[0][j] = j
        for i in range(1,m+1):
            for j in range(1,n+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] + 1,
                    dp[i][j-1] + 1,
                    dp[i-1][j-1] + 1)
        return dp[-1][-1]