动态规划Day16(编辑距离,删除元素待写完)

这篇具有很好参考价值的文章主要介绍了动态规划Day16(编辑距离,删除元素待写完)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

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

看到题目的第一想法               

看到代码随想录之后的想法

自己实现过程中遇到的困难(看代码)

72. 编辑距离

看到题目的第一想法               

看到代码随想录之后的想法

自己实现过程中遇到的困难(看代码)


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

力扣题目链接(opens new window)

给定两个单词 word1 和 word2,找到使得 word1 和 word2 相同所需的最小步数,每步可以删除任意一个字符串中的一个字符。

示例:

  • 输入: "sea", "eat"
  • 输出: 2
  • 解释: 第一步将"sea"变为"ea",第二步将"eat"变为"ea"
看到题目的第一想法
               

         按照求最长子序列的思路来做,得到最长的公共length值,用两个字符串的长度减去两个公共length 就是最长公共子序列的长度

        公共最长子序列的求法

        dp[i][j] 为0~i-1 0~j-1的最长序列

        递推公式

        若相同,dp[i][j] = dp[i-1][j-1]+1

        若不相同,二选一 dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
       

        

看到代码随想录之后的想法

        用动态规划,使用了删除的思路

        (选中两个单词的字符,判断删除哪一个)

        确定dp数组和每个下标的含义

        

        dp[i][j]记录末尾为i-1和j-1的最少删除字符的个数

        

        确定递推公式

        要从递推公式来进行考虑

       若word1[i] = word2[j] 则不管是否选中word1 和word2 和不选中word1和word2都一样,不需要新增删除的次数,总删除的次数和之前相等

                dp[i][j] = dp[i-1][j-1]; 

        若word1[i] !=word2[j] 则从之前的删除次数最小值 来考虑

                若选中word1来删除

                之前的总删除次数为dp[i-1][j]+1

        

                若选中word2来删除

                之前的总删除次数为dp[i][j-1]+1

                若都选中,两者都删

                之前的总删除次数为dp[i-1][j-1]+2

                之前的最长子序列是dp[i][j] = Math.min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+2);

               

         dp数组初始化

                  因为dp[i][j] 代表0~i-1,0~j-1的最大删除次数,

                则dp[i][0] = i

                   dp[0][j] = j (含义:若把j变成0 需要删除j次)

        确定遍历顺序

        从前往后,从上往下

        举例推导dp数组           

        打印dp数组

        打印最后一个元素

自己实现过程中遇到的困难(看代码)

                        疑问?为什么选最小的?不相同时不应该两个都要删吗?
                        不是两个都要删,而是判断不相同了,一次只删一个,选择哪一个
                        两个不相等,模拟一下这个双重循环,其实i固定不变,只是在动j
                       遇到两个单词中不相等的字符,来通过dp来判断应该删除哪一个,二维数组是动态变化的
                     最小的删除个数,从之前中选择最小的

class Solution {
    public int minDistance(String word1, String word2) {
        /*
        //我的做法
        //相同的最小步数
        //其实就是看公共子序列的最大长度?,然后看删去需要多少个字符?
        //确定dp的定义和下标的含义
        // dp[i][j] 0~i-1的word1 和 0~j-1的相同公共子序列的长度
        //确定递推公式
        // 若word[i-1]==word[j-1] 则dp[i][j]=dp[i-1][j-1]+1
        // 若不相等 则dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
        //dp数组初始化
        // 都为0
        //确定遍历顺序
        // 从上往下,从左至右
        //打印dp数组
        int[][] dp = new int[word1.length()+1][word2.length()+1];
        for(int i=1;i<=word1.length();i++){
            for(int j=1;j<=word2.length();j++){
                if(word1.charAt(i-1)==word2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1]+1;
                }else{
                    dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]);
                }
            }
        }
        int maxLength = dp[word1.length()][word2.length()];
        return word1.length()+word2.length()-2*maxLength;*/
        //卡哥的做法
        //确定dp的定义和下标的含义
        // dp[i][j] 代表删除字符的最小的个数
        //确定递推公式
        // 如何删除
        // word1[i-1]==word2[j-1] 若相等 考虑选中word1[i-1] 和word2[j-1] 和不选中word1[i-1]和word2[j-1]
        // dp[i][j] = dp[i-1][j-1],因为相等,所以 都考虑和都不考虑,最小删除的个数都是一样的
        // word1[i]!=word2[j] 若不相等 ,考虑最小删除的个数,有三种情况
        // 若不选中word1 则为 dp[i-1][j]+1
        // 若不选中word2 则为 dp[i][j-1]+1
        // 若不都选中 dp[i-1][j-1] +2 去三者中的最小值
        //dp数组初始化
        // dp[i][0] = i word1 有值,word2为空串 
        // dp[0][j] = j word2 有值,word1为空串
        //确定遍历顺序
        // 从上往下,从左至右
        //打印dp数组
        int dp[][] = new int[word1.length()+1][word2.length()+1];
        for(int i=0;i<=word1.length();i++){
            dp[i][0] = i;
        }
        for(int j=0;j<=word2.length();j++){
            dp[0][j] = j;
        }
        for(int i=1;i<=word1.length();i++){
            for(int j=1;j<=word2.length();j++){
                if(word1.charAt(i-1)==word2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    // 疑问?为什么选最小的?不相同时不应该两个都要删吗?
                    // 不是两个都要删,而是判断不相同了,一次只删一个,选择哪一个
                    // 两个不相等,模拟一下这个双重循环,其实i固定不变,只是在动j
                    // 看两个单词中不相等的字符,来看通过dp来判断应该删除哪一个,二维数组是动态变化的
                    //最小的删除个数,从之前中选择最小的
                    dp[i][j] = Math.min(dp[i-1][j]+1,dp[i][j-1]+1);
                }
            }
        }
        return dp[word1.length()][word2.length()];
    }
}

72. 编辑距离

力扣题目链接(opens new window)

给你两个单词 word1 和 word2,请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作:

  • 插入一个字符

  • 删除一个字符

  • 替换一个字符

  • 示例 1:

  • 输入:word1 = "horse", word2 = "ros"

  • 输出:3

  • 解释: horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e')

  • 示例 2:

  • 输入:word1 = "intention", word2 = "execution"

  • 输出:5

  • 解释: intention -> inention (删除 't') inention -> enention (将 'i' 替换为 'e') enention -> exention (将 'n' 替换为 'x') exention -> exection (将 'n' 替换为 'c') exection -> execution (插入 'u')

提示:

  • 0 <= word1.length, word2.length <= 500
  • word1 和 word2 由小写英文字母组成
看到题目的第一想法
               

       按上一题的思路来做

        

看到代码随想录之后的想法

        用动态规划,使用了删除的思路

        (选中两个单词的字符,判断删除哪一个)

        确定dp数组和每个下标的含义

        

        dp[i][j]记录末尾为i-1和j-1的最少删除字符的个数

        

        确定递推公式

        要从递推公式来进行考虑

       若word1[i] = word2[j] 则不管是否选中word1 和word2 和不选中word1和word2都一样,不需要新增删除的次数,总删除的次数和之前相等

                dp[i][j] = dp[i-1][j-1]; 

        若word1[i] !=word2[j] 则从之前的操作次数最小值 来考虑

                若选中word1来操作一次  (之前的基础上+1)

                替换

                将两个元素看成相等的,那么dp[i][j] = dp[i-1][j-1]+1

                新增和删除

                之前的总操作次数为dp[i-1][j],在这个基础上+1

                若选中word2来操作同理

         dp数组初始化

                  因为dp[i][j] 代表0~i-1,0~j-1的最大操作次数,

                则dp[i][0] = i

                   dp[0][j] = j (含义:若把j变成0 需要删除j次)

        确定遍历顺序

        从前往后,从上往下

        举例推导dp数组           

        打印dp数组

        打印最后一个元素

自己实现过程中遇到的困难(看代码)

                        文章来源地址https://www.toymoban.com/news/detail-819882.html

class Solution {
    public int minDistance(String word1, String word2) {
        //word1 转换成word2需要的最小操作数
        //word1 转换成word2 需要的最小操作数、其实对于word2也能进行操作
        //dp[i][j]代表最小操作数 再进行插入?
        //若相等
        //dp[i][j] = dp[i-1][j-1]
        //若不相等
        //替换:可以视为最终目的让两个元素相等,按两个元素相等来看
        //dp[i][j] = dp[i-1][j-1]+1
        //删除:就是删
        // dp[i][j] = dp[i][j-1]+1;
        //插入:和删除一样,只是逆向操作而已
        // dp[i][j] = dp[i][j-1]+1;
        //dp数组初始化
        //两个单词都能操作
        //dp[i][0] = i
        //dp[0][j] = j
        int[][] dp = new int[word1.length()+1][word2.length()+1];
        for(int i=0;i<=word1.length();i++){
            dp[i][0] = i;
        }
        for(int j=0;j<=word2.length();j++){
            dp[0][j] = j;
        }
        for(int i=1;i<=word1.length();i++){
            for(int j=1;j<=word2.length();j++){
                if(word1.charAt(i-1)==word2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    //替换:为dp[i-1][j-1]+1(判断最小值时不能省略这一步)
                    //为什么上一题可以省略这一步呢?
                    //上一题是求的删除的最小次数,上一题是dp[i-1][j-1]+2 代表两者都不选中时,全删
                    //删除和新增:为dp[i-1][j]+1,dp[i][j-1]+1的最小值
                    dp[i][j] = Math.min(dp[i-1][j-1]+1,Math.min(dp[i-1][j]+1,dp[i][j-1]+1));
                }
            }
        }
        return dp[word1.length()][word2.length()];

    }
}

到了这里,关于动态规划Day16(编辑距离,删除元素待写完)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 编辑距离(动态规划)

    题目描述 给你两个单词 word1 和 word2,请你计算出将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作: 插入一个字符 删除一个字符 替换一个字符 编辑距离:是指两个字符串之间,由一个转成另一个所需的最少编辑操作次数。 问题:word1到word2的

    2023年04月08日
    浏览(36)
  • 力扣72. 编辑距离(动态规划)

    Problem: 72. 编辑距离 由于易得将字符串word1向word2转换和word2向word1转换是等效的,则我们假定统一为word1向word2转换!!! 1.确定状态:我们假设现在有下标i,j分别指向字符串word1和word2 尾部的字符 ,dp(i,j)表示当前的操作则: 1.1. dp(i- 1, j) + 1;表示 删除 ,直接把word1[i]的这个字

    2024年02月21日
    浏览(46)
  • 编辑距离的动态规划

    编辑距离,也称 Levenshtein 距离,指两个字符串之间互相转换的最少修改次数,通常用于在信息检索和自然语言处理中度量两个序列的相似度。 Question 输入两个字符串 (s) 和 (t) ,返回将 (s) 转换为 (t) 所需的最少编辑步数。 你可以在一个字符串中进行三种编辑操作

    2024年04月08日
    浏览(35)
  • 【算法一则】编辑距离 【动态规划】

    给你两个单词 word1 和 word2, 请返回将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作: 插入一个字符 删除一个字符 替换一个字符 这个问题可以使用动态规划来解决。我们可以定义一个二维数组dp,其中dp[i][j]表示将word1的前i个字符转换成word

    2024年04月24日
    浏览(36)
  • 【算法】动态规划算法求(编辑距离)

    目录 编辑距离: 举例: 代码如下 调试: 核心代码: 画图演示上述代码:    是一种计算两个自符串之间差异程度的方法,它通过比较 两个字符串之间的插入,删除和 替换操作的数量 ,来确定他们之间的距离。 现有两个字符串 字符串s1:”CTGA\\\" 字符串s2:  \\\"ACGCTA\\\" 求s1和

    2024年02月12日
    浏览(41)
  • 【Leetcode72】编辑距离(动态规划)

    (1)确定状态 dp[i][j] 表示word1中前 i 个单词,变换到word2中前 j 个字符,最少需要的动作次数。 (2)状态转移方程 编辑距离可以通过以下三种操作进行计算:插入一个字符、删除一个字符、替换一个字符。因此,可以使用以下状态转移方程: 如果 A[i] == B[j] ,那么 dp[i][j]

    2024年02月12日
    浏览(42)
  • Day56 | 583. 两个字符串的删除操作 | 72. 编辑距离

    583. 两个字符串的删除操作 注意点: 1.当word1[i - 1] 与 word2[j - 1]不相同的时候, 情况一:删word1[i - 1],最少操作次数为dp[i - 1][j] + 1 情况二:删word2[j - 1],最少操作次数为dp[i][j - 1] + 1 情况三:同时删word1[i - 1]和word2[j - 1],操作的最少次数为dp[i - 1][j - 1] + 2 因为 dp[i][j-1]+1 = d

    2024年02月08日
    浏览(45)
  • 【动态规划----“最小编辑距离”问题(C++解决)】

    给定两个字符串A和B,以及下列三种字符运算: (1)删除一个字符(2)插入一个字符(3)将一个字符改写为另一个字符 设计算法求将A通过以上三种操作转换为B的最小次数 举例: “xy” = “xz”,只需要把 y 替换成 z,因此,最小编辑距离为 1。 “xyz” = “xy”,只需要删除

    2024年04月25日
    浏览(86)
  • 动态规划问题-最小编辑距离(Minimum Edit Distance)

    我们今天要探讨的动态规划问题来源于俄罗斯科学家Levenshtein提出的两个对象之间的不相似度,在音频、语言翻译等领域有广泛的应用。如果用于评估字符串之间的不相似度,那么又称为最小编辑距离MED(Minimum Edit Distance),它规定从string 1到转换成 string 2的最少操作数,最少操

    2024年02月09日
    浏览(54)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包