代码随想录算法训练营第四十六天 | leetcode：两个字符串的删除操作,编辑距离
0 / 0 / 创建于 10个月前 /
_zzh 的个人博客
583. 两个字符串的删除操作
解题方法
- dp数组的含义：dp[i][j]：下标以i-1为结尾的字符串word1，和下标以j-1为结尾的字符串word2，想要达到相等，所需要删除元素的最少次数
- 确定递推公式：主要就是两大情况： text1[i - 1] 与 text2[j - 1]相同，text1[i - 1] 与 text2[j - 1]不相同
- if (word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1]
因为找到了一个相同的字符，此时不用删除元素，所以延续上一个状态即可.- if (word1[i - 1] ！= word2[j - 1]) dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1)
- 情况1：删word1[i - 1]，最少操作次数为dp[i - 1][j] + 1
- 情况2：删word2[j - 1]，最少操作次数为dp[i][j - 1] + 1
- 情况3：同时删word1[i - 1]和word2[j - 1]，操作的最少次数为dp[i - 1][j - 1] + 2，因为：dp[i][j - 1] + 1 = dp[i - 1][j - 1] + 2。所以上面两个情况已经包含了情况3。所以递推公式可以不考虑情况3
- 初始化dp数组：从递推公式可以看出，dp[i][0] = i; dp[0][j] = j; 因为一个字符长度为i/j,另一个长度为0，而一次只能操作一个字符，所以要把长度为i/j的字符删除i/j次才能变为空字符串。,其余值由初始化值可以推出覆盖，所以初始化多少都可以。统一初始化为0。
- 遍历顺序：从递推公式可以看出dp[i][j]都是依赖于[i - 1][j - 1]，那么遍历顺序也应该是从上到下，从左到右
code
动态规划解法1
class Solution {
/**
* @param String $word1
* @param String $word2
* @return Integer
*/
function minDistance($word1, $word2) {
$len1 = strlen($word1);
$len2 = strlen($word2);
$dp = array_fill(0, $len1 + 1, array_fill(0, $len2 + 1, 0));
for($i = 0; $i <= $len1; $i++) $dp[$i][0] = $i;
for($j = 0; $j <= $len2; $j++) $dp[0][$j] = $j;
for($i = 1; $i <= $len1; $i++){
for($j = 1; $j <= $len2; $j++){
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);
}
}
}
return $dp[$len1][$len2];
}
}复杂度
时间复杂度
O(n x m)其中 n 和 m 分别为 word1 和 word2 的长度
空间复杂度
O(n x m)
动态规划解法2 （先求公共子序列，在计算需要删除字符数）
class Solution {
/**
* @param String $word1
* @param String $word2
* @return Integer
*/
function minDistance($word1, $word2) {
$len1 = strlen($word1);
$len2 = strlen($word2);
$dp = array_fill(0, $len1+1, array_fill(0, $len2+1, 0));
//print_r($dp);
//求公共子序列
for($i = 1; $i <= $len1; $i++){
for($j = 1; $j <= $len2; $j++){
if($word1[$i-1] == $word2[$j-1]){
$dp[$i][$j] = $dp[$i-1][$j-1] + 1;
}else{
$dp[$i][$j] = max($dp[$i-1][$j],$dp[$i][$j-1]);
}
}
}
//因为每步只能删除任意字符串的一个字符，所以求出公共子序列长度后。用两个字符长度之和-2倍的公共子序列长度 = 删除字符个数(需要操作的步数)
return $len1 + $len2 - 2 * $dp[$len1][$len2];
}
}复杂度
时间复杂度
O(n x m)其中 n 和 m 分别为 word1 和 word2 的长度
空间复杂度
O(n x m)
72. 编辑距离
解题方法
- dp数组的含义：dp[i][j] ：以i-1为结尾的word1,转换为以j-1结尾的word2，最少需要操作dp[i][j]次
- 确定递推公式：
- if(word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1]
当s[i - 1] 与 t[j - 1]相等时，dp[i][j]不需要操作，延续上一个状态即可。- if(word1[i - 1] != word2[j - 1]) dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j- 1] + 1, dp[i - 1][j - 1] + 1);
- 删除操作：dp[i - 1][j] + 1: 不考虑word1[i - 2]， 相当于把word1[i - 2]删除，所以操作数需要+1.
- 删除操作：dp[i][j - 1] + 1: 不考虑word2[j - 2]， 相当于把word2[j - 2]删除，所以操作数需要+1.
- 增加操作：而增加的操作相当于删除的的操作。例如word1 = ab, word2 = a; word1删除b的操作就相当于，word2加上b的操作
- 替换操作：dp[i - 1][j - 1] + 1 ：相当于在dp[i - 1][j - 1]的基础上操作一个字符，即可使两个字符相等。例如word1 = ab, word2 = ac; 只需要把word1/word2修改一个字符即可使两个字符相等。
- 初始化dp数组：dp[i][0] = i; dp[0][j] = j; 因为一个字符长度为i/j,另一个长度为0，而一次只能操作一个字符，所以要把长度为i/j的字符删除i/j次才能变为空字符串。其余初始化为0.
- 遍历顺序：递推公式中dp[i][j]依赖于[i - 1][j - 1]的状态，所以遍历顺序从上到下，从左到右。
code
class Solution {
/**
* @param String $word1
* @param String $word2
* @return Integer
*/
function minDistance($word1, $word2) {
$len1 = strlen($word1);
$len2 = strlen($word2);
$dp = array_fill(0, $len1 + 1, array_fill(0, $len2 + 2, 0));
for($i = 0; $i <= $len1; $i++) $dp[$i][0] = $i;
for($j = 0; $j <= $len2; $j++) $dp[0][$j] = $j;
for($i = 1; $i <= $len1; $i++){
for($j = 1; $j <= $len2; $j++){
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[$len1][$len2];
}
}复杂度
时间复杂度
O(n * m)
空间复杂度
O(n * m)
本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号