无锡企业推广网站,宁波seo推广开发,下载字体如何在wordpress,宜兴网站设计文章目录 583. 两个字符串的删除操作抽象化#xff1a;最长公共子序列的长度dp 记录删除元素的数量 72. 编辑距离编辑距离总结篇 583. 两个字符串的删除操作
题目链接 | 解题思路
本题的第一反应应该是进行最长公共子序列的抽象化#xff0c;因为删除元素这个操作看上去很复… 文章目录 583. 两个字符串的删除操作抽象化最长公共子序列的长度dp 记录删除元素的数量 72. 编辑距离编辑距离总结篇 583. 两个字符串的删除操作
题目链接 | 解题思路
本题的第一反应应该是进行最长公共子序列的抽象化因为删除元素这个操作看上去很复杂。但实际上也能通过 dp 来记录删除操作也为后面那道编辑距离打下了基础。
抽象化最长公共子序列的长度
从两个不同的字符串删除元素直到相同也可以理解为找到最长公共子序列之后就删除多余的元素。这样的抽象化后可以直接套用找最长公共子序列的解法在最后用两个字符串的总长度减去两倍的最长公共子序列长度即可。
class Solution:def minDistance(self, word1: str, word2: str) - int:dp [[0] * len(word2) for _ in range(len(word1))]first_row_flag first_col_flag Falsefor j in range(len(word2)):if word1[0] word2[j]:first_row_flag Trueif first_row_flag:dp[0][j] 1for i in range(len(word1)):if word1[i] word2[0]:first_col_flag Trueif first_col_flag:dp[i][0] 1for i in range(1, len(word1)):for j in range(1, len(word2)):if word1[i] word2[j]:dp[i][j] dp[i-1][j-1] 1else:dp[i][j] max(dp[i-1][j], dp[i][j-1])return len(word1) len(word2) - 2 * dp[-1][-1]dp 记录删除元素的数量
删除元素看着很复杂因为从结果上来看删除这个步骤可以发生在任一字符串的任一位置没办法通过 dp 找到规律。但实际上只要在 dp 的递推中正确递推了最优解那就可以解题。
初始化终于变的复杂了不能再直接初始化第一行和第一列。对于这样的数据构造对应 的第0行和第0列才是正道
dp 数组的下标含义dp[i][j] 是 word1[:i] 和 word2[:j] 能够达到相同需要的最少删除数这里定义的改变和后面的dp 递推公式 如果 word1[i] word2[j]那么不需要对这两个尾部元素进行任何删除dp[i][j] dp[i-1][j-1]否则必然要至少删掉一个元素才能使得有可能使得两个字符串能够匹配所以 dp[i][j] min(dp[i-1][j], dp[i][j-1]) 注意当然有可能这两个尾部元素都需要删除但这个情况 dp[i-1][j-1] 2 被包含在了 dp[i-1][j], dp[i][j-1] 中可以不需要额外考虑 dp 的初始化 对于 word1 来说需要删除 word2[:j] 中所有的元素才行也就是 dp[0][j] j同理dp[i][0] i dp 遍历顺序从上到下、从左到右即可举例推导word1 sea, word2 eat
‘’sea‘’0123e1212a2321t3432
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][j-1], dp[i-1][j]) 1return dp[-1][-1]72. 编辑距离
题目链接 | 解题思路 dp 数组的下标含义dp[i][j] 是将 word1[:i] 转换成 word2[:j] 的最少操作数定义和初始化有点关系类似于背包问题 dp 递推公式 如果 word1[i-1] word2[j-1]那么各自的结尾元素不需要进行任何操作直接转换成之前的子问题dp[i][j] dp[i-1][j-1]否则我们显然需要进行一次操作insert、delete、change才能转换成之前的子问题 如果需要进行 insert显然我们是希望在 word1[:i] 的后面加上一个 word2[i-1]这样将当前问题转换成了子问题“将 word1[:i] 转换成 word2[:j-1]”dp[i][j] dp[i][j-1] 1如果需要进行 delete显然我们是希望删除 word1[i-1]这样将当前问题转换成了子问题“将 word1[:i-1] 转换成 word2[:j]”dp[i][j] dp[i-1][j] 1如果需要进行 change显然我们是希望将 word1[i-1] 变成 word2[j-1]这样将当前问题转换成了子问题“将 word1[:i-1] 转换成 word2[:j-1]”dp[i][j] dp[i-1][j-1] 1 由于我们需要记录最小操作数所以 dp[i][j] min([dp[i-1][j-1], dp[i-1][j], dp[i][j-1]]) 1 dp 数组的初始化本题如果直接进行第一行和第一列的初始化难度无疑逆天所以才用了背包问题一样处理 的定义来帮助初始化 对于 i0 (word1 )将其转化成 word2[:j] 显然需要 j 次操作insert所以 dp[0][j] j对于 j0 (word2 )将 word2[:i] 其转化成 显然需要 i 次操作delete所以 dp[i][0] i这样的初始化比真正处理长度为 1 的 word1, word2 要正常多了 dp 的遍历顺序递推依赖左上方的元素从上到下、从左到右即可 举例说明word1 horse, word2 ros ros0123h1123o2212r3222s4332e5443
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][j-1], dp[i-1][j]]) 1return dp[-1][-1]编辑距离总结篇
编辑距离总结
在之前的讲解中或多或少提到了编辑距离。那些题目或多或少都有一些别的解法或者看作是重复字数组、重复子序列的变种。但是实际上他们都能被看作是编辑距离这个终极版本的削弱版本
判断子序列 可以看作只允许删除 t 的元素的情况下能否得到 s不同的子序列 可以看作有多少种删除 t 的元素的方法能够得到 s两个字符串的删除操作 可以看作允许删除两个字符串的元素使其相同所需要的最少操作数编辑距离 就是真正的编辑距离
