代码随想录算法训练营第四十六天 | leetcode：两个字符串的删除操作,编辑距离

_zzh 的个人博客 / 15 / 0 / 创建于 1个月前 / 更新于 1个月前

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];
    }
}