编辑距离、编辑距离总结

题目给我们两个字符串问两个字符串最少可以删除多少个元素使这两个字符串相同。

本题相对于115.

数组及其下标的含义比较两个字符串里的每个元素是否相同的情况就定义二维数组dp[i][j]以

i-1

是为了方便初始化递推公式ifword1[i-1]word2[j-1]dp[i][j]dp[i-1][j-1]

因为这两个元素已经相同了考虑与不考虑都是一样的因此直接继承dp[i-1][j-1]因为两个元素都相同了就可以不操作它们了。

else

的情况就需要删除元素了如果删除word1[i-1]dp[i][j]dp[i-1][j]1

word1[i-1]如果删除word2[j-1]dp[i][j]dp[i][j-1]1

dp[i][j]dp[i-1][j-1]2。

因此如果两个元素不相同就是

数组的初始化根据递推公式得到推导方向因此第一行和列都需要初始化dp[0][j]

为结尾即空字符串

个元素。

其余下标因为会被覆盖因此默认即可遍历顺序从推导方向可以看出就是从左到右从上到下

forint

dp[word1.length()][word2.length()]打印

数组用于

最长公共子序列一样求出最长公共子序列然后两个原字符串总和相加减去

1.2

dp[word1.length()][word2.length()];}

//DP

数组及其下标的含义比较两个字符串的相同情况我们要定义一个二维数组dp[i][j]以

i-1

结尾是为了方便初始化递推公式要求相同就要比较每个元素讨论它们相同与不相同的情况

ifword1[i-1]word2[j-1]dp[i][j]dp[i-1][j-1]

因为两个元素都相同了就可以不改变操作次数不需要任何操作。

else

word1

个元素dp[i][j]dp[i][j-1]1如果两个元素不相同选择替换元素无论是替换

word1

dp[i][j]Math.min三者取最小值。

为什么这里没有添加元素的操作呢因为对

word1

数组的初始化根据递推公式得到推导方向因此我们要初始化第一行和列都初始化了dp[i][0]也就是以

i-1

i0iword1.length()idp[i][0]idp[0][j]以-1

word1

j0jword2.length()jdp[0][j]j。

为什么取等于号因为

i-1

为结尾的一定要取等了才能表示最后一个元素为结尾。

其余下标无所谓会被覆盖默认为

即可。

遍历顺序根据递推公式和推导方向就一定是从左到右和从上到下forint

dp[word1.length()][word2.length()]打印

数组用于

其实是可以用双指针或者贪心的的但是我在开篇的时候就说了这是编辑距离的入门题目因为从题意中我们也可以发现只需要计算删除的情况不用考虑增加和替换的情况。

(s[i

t[2]是相同的但是字符串s也可以不用s[3]来匹配即用s[0]s[1]s[2]组成的bag。

当然也可以用s[3]来匹配即s[0]s[1]s[3]组成的bag。

t[j

不同的子序列相比其实就是两个字符串可以都可以删除了情况虽说复杂一些但整体思路是不变的。

当word1[i

编辑距离终于来了有了前面三道题目的铺垫应该有思路了本题是两个字符串可以增删改比392.

判断子序列、115.

1]相等了那么就不用编辑了以下标i-2为结尾的字符串word1和以下标j-2为结尾的字符串word2的最近编辑距离dp[i

1][j

在下面的讲解中如果哪里看不懂就回想一下dp[i][j]的定义就明白了。

(word1[i

“a”word2添加一个元素d也就是相当于word1删除一个元素d操作数是一样

1]使其与word2[j