583.两个字符串的删除操作

题目链接：https://leetcode.com/problems/delete-operation-for-two-strings

解法：

1. 确定dp数组（dp table）以及下标的含义

dp[i][j]：以i-1为结尾的字符串word1，和以j-1位结尾的字符串word2，想要达到相等，所需要删除元素的最少次数。

2. 确定递推公式

  • 当word1[i – 1] 与 word2[j – 1]相同的时候
  • 当word1[i – 1] 与 word2[j – 1]不相同的时候

当word1[i – 1] 与 word2[j – 1]相同的时候，dp[i][j] = dp[i – 1][j – 1];

当word1[i – 1] 与 word2[j – 1]不相同的时候，有三种情况：

情况一：删word1[i – 1]，最少操作次数为dp[i – 1][j] + 1

情况二：删word2[j – 1]，最少操作次数为dp[i][j – 1] + 1

情况三：同时删word1[i – 1]和word2[j – 1]，操作的最少次数为dp[i – 1][j – 1] + 2。但这种情况其实可以归并到前两种情况的其中一种，或者说前两中情况又可以由这种情况得到，所以不用单独写了。

于是不相等时，dp[i][j] = min(dp[i][j-1] + dp[i-1][j]) + 1

边界条件：无

时间复杂度：O(n * m)

空间复杂度：O(n * m)

class Solution(object):def minDistance(self, word1, word2):dp = [[0] * (len(word2)+1) for i 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:# 可由word1或者word2删除1个元素递推得到dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1return dp[-1][-1]

72.编辑距离

题目链接：https://leetcode.com/problems/edit-distance/

解法：

1. dp数组和下标的含义

dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]。

2. 递推公式

word1[i-1] != word2[j-1]时，三种操作：

以 word1 为 “horse”，word2 为 “ros”，且 dp[5][3] 为例，即要将 word1的前 5 个字符转换为 word2的前 3 个字符，也就是将 horse 转换为 ros，因此有：

(1) dp[i-1][j-1]，即先将 word1 的前 4 个字符 hors 转换为 word2 的前 2 个字符 ro，然后将第五个字符 word1[4]（因为下标基数以 0 开始） 由 e 替换为 s（即替换为 word2 的第三个字符，word2[2]）

(2) dp[i][j-1]，即先将 word1 的前 5 个字符 horse 转换为 word2 的前 2 个字符 ro，然后在末尾补充一个 s，即插入操作

(3) dp[i-1][j]，即先将 word1 的前 4 个字符 hors 转换为 word2 的前 3 个字符 ros，然后删除 word1 的第 5 个字符

所以插入和删除的操作都是针对word1去做的。

边界条件：无

时间复杂度：O(mn)

空间复杂度：O(mn)

class Solution(object):def minDistance(self, word1, word2):dp = [[0] * (len(word2)+1) for i 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] = j for 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]