在厦门做网站找谁,wordpress旅游模板下载,旅游景点网页,展馆展示设计公司排名前十名LeetCode-72. 编辑距离【字符串 动态规划】 题目描述#xff1a;解题思路一#xff1a;动规五部曲解题思路二#xff1a;动态规划【版本二】解题思路三#xff1a;0 题目描述#xff1a;
给你两个单词 word1 和 word2#xff0c; 请返回将 word1 转换成 word2 所使用的最… LeetCode-72. 编辑距离【字符串 动态规划】 题目描述解题思路一动规五部曲解题思路二动态规划【版本二】解题思路三0 题目描述
给你两个单词 word1 和 word2 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作
插入一个字符 删除一个字符 替换一个字符
示例 1
输入word1 “horse”, word2 “ros” 输出3 解释 horse - rorse (将 ‘h’ 替换为 ‘r’) rorse - rose (删除 ‘r’) rose - ros (删除 ‘e’) 示例 2
输入word1 “intention”, word2 “execution” 输出5 解释 intention - inention (删除 ‘t’) inention - enention (将 ‘i’ 替换为 ‘e’) enention - exention (将 ‘n’ 替换为 ‘x’) exention - exection (将 ‘n’ 替换为 ‘c’) exection - execution (插入 ‘u’)
提示
0 word1.length, word2.length 500 word1 和 word2 由小写英文字母组成
此题的解题思路与LeetCode-1143. 最长公共子序列【字符串 动态规划】非常一致
解题思路一动规五部曲
确定dp数组dp table以及下标的含义 dp[i][j] 表示以下标i-1为结尾的字符串word1和以下标j-1为结尾的字符串word2最近编辑距离为dp[i][j]。
有同学问了为啥要表示下标i-1为结尾的字符串呢为啥不表示下标i为结尾的字符串呢
为什么这么定义我在 718. 最长重复子数组 (opens new window)中做了详细的讲解。
其实用i来表示也可以 用i-1就是为了方便后面dp数组初始化的。
确定递推公式 在确定递推公式的时候首先要考虑清楚编辑的几种操作整理如下
if (word1[i - 1] word2[j - 1])不操作
if (word1[i - 1] ! word2[j - 1])增删换也就是如上4种情况。
if (word1[i - 1] word2[j - 1]) 那么说明不用任何编辑dp[i][j] 就应该是 dp[i - 1][j - 1]即dp[i][j] dp[i - 1][j - 1];
此时可能有同学有点不明白为啥要即dp[i][j] dp[i - 1][j - 1]呢
那么就在回顾上面讲过的dp[i][j]的定义word1[i - 1] 与 word2[j - 1]相等了那么就不用编辑了以下标i-2为结尾的字符串word1和以下标j-2为结尾的字符串word2的最近编辑距离dp[i - 1][j - 1]就是 dp[i][j]了。
在下面的讲解中如果哪里看不懂就回想一下dp[i][j]的定义就明白了。
在整个动规的过程中最为关键就是正确理解dp[i][j]的定义
if (word1[i - 1] ! word2[j - 1])此时就需要编辑了如何编辑呢
操作一word1删除一个元素那么就是以下标i - 2为结尾的word1 与 j-1为结尾的word2的最近编辑距离 再加上一个操作。 即 dp[i][j] dp[i - 1][j] 1;
操作二word2删除一个元素那么就是以下标i - 1为结尾的word1 与 j-2为结尾的word2的最近编辑距离 再加上一个操作。 即 dp[i][j] dp[i][j - 1] 1;
这里有同学发现了怎么都是删除元素添加元素去哪了。
word2添加一个元素相当于word1删除一个元素例如 word1 “ad” word2 “a”word1删除元素’d’ 和 word2添加一个元素’d’变成word1“a”, word2“ad” 最终的操作数是一样 dp数组如下图所示意的 a a d---------- ---------------| 0 | 1 | | 0 | 1 | 2 |---------- ---------------a | 1 | 0 | a | 1 | 0 | 1 |---------- ---------------d | 2 | 1 |----------操作三替换元素word1替换word1[i - 1]使其与word2[j - 1]相同此时不用增删加元素。
可以回顾一下if (word1[i - 1] word2[j - 1])的时候我们的操作 是 dp[i][j] dp[i - 1][j - 1] 对吧。
那么只需要一次替换的操作就可以让 word1[i - 1] 和 word2[j - 1] 相同。
所以 dp[i][j] dp[i - 1][j - 1] 1;
综上当 if (word1[i - 1] ! word2[j - 1]) 时取最小的即dp[i][j] min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) 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 - 1][j], dp[i][j - 1]}) 1;
}dp数组如何初始化 再回顾一下dp[i][j]的定义
dp[i][j] 表示以下标i-1为结尾的字符串word1和以下标j-1为结尾的字符串word2最近编辑距离为dp[i][j]。
那么dp[i][0] 和 dp[0][j] 表示什么呢
dp[i][0] 以下标i-1为结尾的字符串word1和空字符串word2最近编辑距离为dp[i][0]。
那么dp[i][0]就应该是i对word1里的元素全部做删除操作即dp[i][0] i;
同理dp[0][j] j;
确定遍历顺序 从如下四个递推公式
dp[i][j] dp[i - 1][j - 1] dp[i][j] dp[i - 1][j - 1] 1 dp[i][j] dp[i][j - 1] 1 dp[i][j] dp[i - 1][j] 1 可以看出dp[i][j]是依赖左方上方和左上方元素的如图 所以在dp矩阵中一定是从左到右从上到下去遍历。
举例推导dp数组 以示例1为例输入word1 “horse”, word2 ros为例dp矩阵状态图如下
class Solution:def minDistance(self, word1: str, word2: str) - int:dp [[0] * (len(word2)1) for _ in range(len(word1)1)]for i in range(len(word1)1):dp[i][0] ifor j in range(len(word2)1):dp[0][j] jfor i in range(1, len(word1)1):for j in range(1, len(word2)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-1][j], dp[i][j-1]) 1return dp[-1][-1]时间复杂度O(nm) 空间复杂度O(nm)
解题思路二动态规划【版本二】
class Solution:def minDistance(self, word1: str, word2: str) - int:m, n len(word1), len(word2)dp [[0] * (n1) for _ in range(m1)]for i in range(m1):dp[i][0] ifor j in range(n1):dp[0][j] jfor i in range(1, m1):for j in range(1, n1):if word1[i-1] word2[j-1]:dp[i][j] dp[i-1][j-1]else:dp[i][j] min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) 1return dp[-1][-1]时间复杂度O(nm) 空间复杂度O(nm)
解题思路三0 时间复杂度O(n) 空间复杂度O(n)
