当前位置: 首页 > news >正文

代码随想录算法训练营Day56 || ● 583. 两个字符串的删除操作 ● 72. 编辑距离

今天接触到了真正的距离,但可以通过增删改操作来逼近。

问题1:583. 两个字符串的删除操作 - 力扣(LeetCode)

给定两个单词 word1 和 word2 ,返回使得 word1 和  word2 相同所需的最小步数

每步 可以删除任意一个字符串中的一个字符。

思路:该题关键在于理解删除,删除操作即多走一步,由之前的状态进行推导。首先dp[i][j]还是表示从s[i]到t[j]需要的步数,初始化时是从0到s[i]所需删除元素,故为i。通过观察易发现dp可由dp[i-1]j-1],dp[i-1][j],p[i][j-1]得出,代码如下:

class Solution {
public:int minDistance(string word1, string word2) {vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1));for(int i = 0;i <= word1.size();i++) dp[i][0] = i;for(int j = 0;j <= word2.size();j++) dp[0][j] = j;for(int i = 1; i <= word1.size();i++){for(int j = 1;j <= word2.size();j++){if(word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1];else dp[i][j] = min(dp[i][j-1]+1,dp[i-1][j]+1);}}return dp[word1.size()][word2.size()]; }};

问题2:72. 编辑距离 - 力扣(LeetCode)

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

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

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

思路:该题一上来我就去寻找规律,并没有尝试去真正理解增删改操作怎么去替代,并且在绘制例子矩阵时也较为粗心,导致最后找出来的规律是错误的。其实这类题目并没有什么套路,想想怎样将题目允许的变化做相应操作即可,具体代码如下:

class Solution {
public:int minDistance(string word1, string word2) {vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1));for(int i = 0;i < word1.size();i++) dp[i][0] = i;for(int j = 0;j <= word2.size();j++) dp[0][j] = j;for(int i = 1;i <= word1.size();i++){for(int j = 1;j<=word2.size();j++){if(word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1];else dp[i][j] = min({dp[i][j-1],dp[i-1][j],dp[i-1][j-1]}) + 1;}}return dp[word1.size()][word2.size()];}
};

http://www.lryc.cn/news/164196.html

相关文章:

  • chrome_elf.dll丢失怎么办?修复chrome_elf.dll文件的方法
  • 代码随想录32|738.单调递增的数字,968.监控二叉树,56. 合并区间
  • BIO NIO AIO演变
  • JVM GC垃圾回收
  • 【数据结构】队列知识点总结--定义;基本操作;队列的顺序实现;链式存储;双端队列;循环队列
  • 嵌入式学习之链表
  • 静态代理和动态代理笔记
  • [SM6225][Android13]user版本默认允许root和remount
  • pyinstaller打包exe,使用wexpect的问题
  • OpenCV(三十三):计算轮廓面积与轮廓长度
  • 9.11作业
  • AI伦理与未来社会:探讨人工智能的道德挑战与机会
  • Android窗口层级(Window Type)分析
  • 微信小程序基础加强总结
  • 【JAVA - List】差集removeAll() 四种方法实现与优化
  • sql注入基本概念
  • AIGC系列:1.chatgpt可以用来做哪些事情?
  • End-to-End Object Detection with Transformers(论文解析)
  • 生成多样、真实的评论(2019 IEEE International Conference on Big Data )
  • 项目中应该使用nginx还是拦截器来封禁IP
  • SMB 协议详解之-NTLM身份认证
  • day34 Set
  • 数据库_之常用API的使用
  • CTreeCtrl自绘
  • 目标检测YOLO实战应用案例100讲-基于深度学习的可见光遥感图像目标检测
  • MySQL数据库——存储引擎(2)-存储引擎特点(InnoDB、MyISAM、Memory)、存储引擎选择
  • 【Vue】构建vue项目的几种方法以及区别
  • 动态封装对象,属性来自json
  • 【LeetCode-中等题】90. 子集 II
  • Docker如何安装seafile