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

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

解题方法

  1. dp数组的含义:dp[i][j]:下标以i-1为结尾的字符串word1,和下标以j-1为结尾的字符串word2,想要达到相等,所需要删除元素的最少次数
  2. 确定递推公式:主要就是两大情况: 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
  3. 初始化dp数组:从递推公式可以看出,dp[i][0] = i; dp[0][j] = j; 因为一个字符长度为i/j,另一个长度为0,而一次只能操作一个字符,所以要把长度为i/j的字符删除i/j次才能变为空字符串。,其余值由初始化值可以推出覆盖,所以初始化多少都可以。统一初始化为0。
  4. 遍历顺序:从递推公式可以看出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. 编辑距离

解题方法

  1. dp数组的含义:dp[i][j] :以i-1为结尾的word1,转换为以j-1结尾的word2,最少需要操作dp[i][j]次
  2. 确定递推公式:
    • 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修改一个字符即可使两个字符相等。
  3. 初始化dp数组:dp[i][0] = i; dp[0][j] = j; 因为一个字符长度为i/j,另一个长度为0,而一次只能操作一个字符,所以要把长度为i/j的字符删除i/j次才能变为空字符串。其余初始化为0.
  4. 遍历顺序:递推公式中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 协议》,转载必须注明作者和本文链接
《L01 基础入门》
我们将带你从零开发一个项目并部署到线上,本课程教授 Web 开发中专业、实用的技能,如 Git 工作流、Laravel Mix 前端工作流等。
《L03 构架 API 服务器》
你将学到如 RESTFul 设计风格、PostMan 的使用、OAuth 流程,JWT 概念及使用 和 API 开发相关的进阶知识。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!