代码编织梦想

编辑距离问题

题目关键点
115. 不同的子序列 - 力扣(LeetCode)*dp数组定义,情况讨论
583. 两个字符串的删除操作 - 力扣(LeetCode)两个字符串删除,情况讨论多加一种
72. 编辑距离 - 力扣(LeetCode)删除 == 添加 、替换操作?
  • 115. 不同的子序列 - 力扣(LeetCode)

    1. 确定dp数组(dp table)以及下标的含义

      dp[i][j]以i-1为结尾的s子序列中出现以j-1为结尾的t的个数dp[i][j]

      这样定义,注定s中要删除元素,满足t的条件。比如s:bagg,t:bag,那么就需要s中删除元素满足t的条件。

    本题刚开始的dp数组定义就与之前子序列的定义不同,所以分析方法也不同。

    1. 确定递推公式:这一类问题,基本是要分析两种情况

      • s[i - 1] 与 t[j - 1]相等时,dp[i][j]可以有两部分组成。

        • 一部分是用s[i - 1]来匹配,那么个数不变,还是看上一个序列的个数dp[i - 1][j - 1]。-
        • 一部分是不用s[i - 1]来匹配,个数为dp[i - 1][j]。因为s序列中可能出现重复的部分。

        例如: s:bagg 和 t:bag ,s[3] 和 t[2]是相同的,但是字符串s也可以不用s[3]来匹配,即用s[0]s[1]s[2]组成的bag。当然也可以用s[3]来匹配,即:s[0]s[1]s[3]组成的bag。

      • s[i - 1] 与 t[j - 1] 不相等

        • dp[i][j]只有一部分组成,不用s[i - 1]来匹配(就是模拟在s中删除这个元素),即:dp[i - 1][j]

        所以递推公式为:dp[i][j] = dp[i - 1][j];

  1. dp数组如何初始化

    从递推公式dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; 和 dp[i][j] = dp[i - 1][j]; 中可以看出dp[i][j] 是从上方和左上方推导而来,那么dp[i][0]dp[0][j]是一定要初始化的。

    • dp[i][0] 表示:以i-1为结尾的s可以随便删除元素,出现空字符串的个数。那么dp[i][0]一定都是1,因为把以i-1为结尾的s,删除所有元素,出现空字符串的个数就是1。

    • dp[0][j]:空字符串s可以随便删除元素,出现以j-1为结尾的字符串t的个数。那么dp[0][j]一定都是0,s如论如何也变成不了t。

    • dp[0][0]应该是1,空字符串s,可以删除0个元素,变成空字符串t。

  2. 遍历的时候一定是从上到下,从左到右,这样保证dp[i][j]可以根据之前计算出来的数值进行计算。

    class Solution {
        public int numDistinct(String s, String t) {
            int m = s.length();
            int n = t.length();
            int [][] dp = new int [m + 1][n + 1];
            //dp数组的初始化
            for(int i = 1 ; i <= m ; i ++){
                dp[i][0] = 1;
            }
            for(int i = 1 ; i <= n ; i ++){
                dp[0][i] = 0;
            }
            dp[0][0] = 1;
            for(int i = 1 ; i <= m ; i ++){
                char s1 = s.charAt(i - 1);
                for(int j = 1 ; j <= n ; j ++){
                    char t1 = t.charAt(j - 1);
                    //s1 == t1 存在两种情况,不用s[i - 1]匹配 + 用s[i - 1]匹配
                    if(s1 == t1) dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
                    //s1 != t1 只有一种情况,不用s[i - 1]匹配。
                    else dp[i][j] = dp[i - 1][j];
    
                   // System.out.println("以s[" + (i - 1) + "]结尾的字符串中,以t[" + (j - 1) +"]结尾的子序列的个数为" + dp[i][j]);
                }
            }
            return dp[m][n];
        }
    }
    
  • 583. 两个字符串的删除操作 - 力扣(LeetCode)

    1. dp定义:dp[i][j]:以i - 1结尾的word1和以j - 1结尾的word2,删除字符后使两个单词相等的最小删除步数为dp[i][j]

    2. dp数组推导:

      word1[i - 1] = word2[j - 1]:不需要删除:dp[i][j] = dp[i - 1][j - 1]

      word1[i - 1] != word2[j - 1]:需要删除:删除word1或删除word2dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1)

      dp[i - 1][j],此时dp数组的定义为以i - 2结尾的word1和以j - 1结尾的word2,删除字符后使两个单词相等的最小删除步数。

      相当于从dp数组定义上删除了i - 1这个字符。

    3. 初始化:dp[i][0]:word2为空字符串,以i-1为结尾的字符串word1要删除多少个元素,才能和word2相同呢,很明显dp[i][0] = idp[0][j]的话同理。

    4. 遍历顺序从前往后,从上往下遍历。

    5. 举例推导dp

      class Solution {
          public int minDistance(String word1, String word2) {
              int m = word1.length();
              int n = word2.length();
              int [] [] dp = new int [m + 1][n + 1];
              for(int i = 0 ; i <= m ; i ++){
                  dp[i][0] = i;
              }
              for(int j = 0 ; j <= n ; j ++){
                  dp[0][j] = j;
              }
              for(int i = 1 ; i <= m ; i ++){
                  char w1 = word1.charAt(i - 1);
                  for(int j = 1 ; j <= n ; j ++){
                      char w2 = word2.charAt(j - 1);
                      if(w1 == w2) dp[i][j] = dp[i - 1][j - 1];
                      else dp[i][j] = Math.min(dp[i - 1][j] + 1 , dp[i][j - 1] + 1);
                      
                      //System.out.println("以word1[" + (i - 1) + "]和word[" + (j - 1) + "]结尾的单词,最少需要" + dp[i][j] + "步删除才能使word1与word2相等");
                  }
              }
              return dp[m][n];
          }
      }
      
  • 72. 编辑距离 - 力扣(LeetCode)

    1. dp[i][j]:以i - 1结尾的word1和以j - 1结尾的word2,转换所需的最小操作数为dp[i][j]

    2. word1[i - 1] == word2[j - 1] :不需要进行操作,dp[i][j] = dp[i - 1][j - 1]

      word1[i - 1] != word2[j - 1]:需要进行操作:

      删除(添加):word2删除一个元素,相当于word1添加一个元素。

      word1删除一个元素:dp[i][j] = dp[i - 1][j] + 1

      word2删除一个元素(word1添加元素):dp[i][j] = dp[i][j - 1] + 1

      替换:可以回顾一下,if (word1[i - 1] == word2[j - 1])的时候我们的操作 是 dp[i][j] = dp[i - 1][j - 1] 对吧。

      那么只需要一次替换的操作,就可以让 word1[i - 1] 和 word2[j - 1] 相同。所以 dp[i][j] = dp[i - 1][j - 1] + 1;

      这里的替换操作不需要考虑具体细节,只需要想,替换操作就是把不同的数替换为相同的数,比相同时的操作要多一步。

    3. dp数组初始化:dp[i][0] :以下标i-1为结尾的字符串word1,和空字符串word2,最近编辑距离为dp[i][0]

      那么dp[i][0]就应该是i,对word1里的元素全部做删除操作,即:dp[i][0] = i;

      同理dp[0][j] = j;

    4. 从上往下,从左往右遍历。

    5. 举例推导dp数组

      class Solution {
          public int minDistance(String word1, String word2) {
              int m = word1.length();
              int n = word2.length();
              int [] [] dp = new int [m + 1][n + 1];
              for(int i = 0 ; i <= m ; i ++){
                  dp[i][0] = i;
              }
              for(int j = 0 ; j <= n ; j ++){
                  dp[0][j] = j;
              }
              for(int i = 1 ; i <= m ; i ++){
                  char w1 = word1.charAt(i - 1);
                  for(int j = 1 ; j <= n ; j ++){
                      char w2 = word2.charAt(j - 1);
                      if(w1 == w2) dp[i][j] = dp[i - 1][j - 1];
                      else dp[i][j] = Math.min(dp[i - 1][j - 1] + 1 , Math.min(dp[i - 1][j] + 1 , dp[i][j - 1] + 1));
                      
                      //System.out.println("以word1[" + (i - 1) + "]和word2[" + (j - 1) + "]结尾的单词,word1最少需要" + dp[i][j] + "步操作才能使word1与word2相等");
                  }
              }
              return dp[m][n];
          }
      }
      

总结

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_62633072/article/details/129828385

Java后端开发学习路线:一文串起所有主流技术点-爱代码爱编程

注:本文已经收录进开源项目:github.com/JavaCollection,有自学路线、面试题和面经、编程资料以及系列技术文章。 前言 这篇想写很久了,原以为一两天搞定,结果整理、串接、画图搞了一周多。经过一番梳理、虽然东西不少,但感觉还是挺清晰的,不说了,肝。 前方高能 一图胜千言,但凡能用图,就不想用文字。直接看图吧,看完再聊

☀️苏州程序大白一文教你学会微信小程序开发☀️《❤️记得收藏❤️》-爱代码爱编程

☀️苏州程序大白一文教你学会微信小程序开发☀️《❤️记得收藏❤️》 目录 🏳️‍🌈开讲啦!!!!🏳️‍🌈苏州程序大白🏳️‍🌈🌟博主介绍🌠前言🌠讲讲专享小程序有什么优势?🌠小程序文件分析🌠事件绑定🔥图片问题🔥轮播图swiper💧自定义组件💧生命周期🌐页面生命周期🌐项目制作🌐缓冲事件🌐`es7 async`语法🌐触底事件❄️下拉刷新页面❄️cs

☀️苏州程序大白一文让你学会Java Servlet基础☀️《❤️记得收藏❤️》-爱代码爱编程

☀️苏州程序大白一文让你学会Java Servlet基础☀️《❤️记得收藏❤️》 目录 🏳️‍🌈开讲啦!!!!🏳️‍🌈苏州程序大白🏳️‍🌈🌟博主介绍🍇1、前言🍈2、阐述 Servlet 和 CGI 的区别?🍉3、Servlet 接口中有哪些方法及 Servlet 生命周期探秘🍊4、get 和 post 请求的区别🍋5、什么情况下调用 doG

☀️苏州程序大白一文从基础手把手教你Python数据可视化大佬☀️《❤️记得收藏❤️》-爱代码爱编程

☀️苏州程序大白一文从基础手把手教你Python数据可视化大佬☀️《❤️记得收藏❤️》 目录 🏳️‍🌈开讲啦!!!!🏳️‍🌈苏州程序大白🏳️‍🌈🌟博主介绍前言数据关系可视化散点图 Scatter plots折线图强调连续性 Emphasizing continuity with line plots同时显示多了图表数据种类的可视化 Plot

Python 实操案例:一文详解10种聚类算法-爱代码爱编程

聚类或聚类分析是无监督学习问题。它通常被用作数据分析技术,用于发现数据中的有趣模式,例如基于其行为的客户群。有许多聚类算法可供选择,对于所有情况,没有单一的最佳聚类算法。相反,最好探索一系列聚类算法以及每种算法的不同配置。在本教程中,你将发现如何在 python 中安装和使用顶级聚类算法。 完成本教程后,你将知道: 聚类是在输入数据的特征空间中查找自

一文解决安装anaconda后c盘不断增加的问题、修改默认配置_橙子园的博客-爱代码爱编程

这个问题主要原因是由于Anaconda默认安装虚拟环境以及pkg在c盘的问题,有些同学在安装Anacoda时明明选择了其他安装路径,但是C盘还是不断在增加。 下面我们来解决,这里其实有两种解决方式一种是通过添加dir来替换默认路径、一种是直接配置c盘路径下的.condarc文件,请记住这两种方法一定是再安装anaconda时选择的是Just Me,如果你选

一文解决openssl ssl_read: connection was reset, errno 10054问题_念兮为美的博客-爱代码爱编程

文章目录 1. 复现问题2. 分析问题3. 解决办法 1. 复现问题 drawio是免费的画图神器,因而,今天尝试从github上下载drawio,如下图所示: 复制下载地址到git bash中,却报出

❤️一文掌握html+css+js开发小说阅读器❤️_js小说阅读器-爱代码爱编程

上周《让CSS3中Transform属性带你一文实现炫酷的转盘抽奖效果》博文中说到这周出一篇介绍小说阅读器开发的博文,可能是离职不上班的原因,在家变得也懒散了一些,本来是打算上周三时候动手开发的,一直拖到了昨天才开始开发,花