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

LeetCode583:两个字符串的删除操作

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

代码如下:

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(min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1] + 2);
                }
            }
        }

        return dp[word1.size()][word2.size()];
    }
};

dp的含义:以i-1的word1和j-1的word2两个字符串删除使得相同的最小步数

这里的i-1和j-1是为了方便后续的初始化。

dp的递推公式

if(word1[i - 1] == word2[j - 1])

{
           dp[i][j] = dp[i - 1][j - 1];
}
else
{
            dp[i][j] = min(min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1] + 2);
}

这个其实还是这么判断嘛,这两个相同的话,那么就直接让两个字符串往前走即可,这个时候不需要删除,如果不相同的话,那么这个时候,第一种情况就是word1串删除,也就是dp[i - 1][j] + 1,第二种情况是dp[i][j - 1] + 1的操作,第三种就是这两个都执行删除操作,然后加上2,又因为是求最小的步数嘛,所以就需要这三个最小值即可

初始化:这个初始化其实是需要在dp[i][0]初始化成i,在dp[0][j]初始化成j,因为dp[i][j]这个需要我们有初始化的值,才能往后进行推导

遍历顺序:

这个题目仍然可以通过由左到右,由上到下可以推导出来这个dp,那么遍历顺序就直接按照正常即可

返回值:这个题目返回值仍然是两个各自的字符串长度。


http://www.kler.cn/a/371872.html

相关文章:

  • Python小白学习教程从入门到入坑------第二十课 闭包修饰器(语法基础)
  • Java NIO2 异步IO支持
  • Flume采集Kafka数据到Hive
  • LabVIEW汽车状态监测系统
  • 中阳智能投资系统:量化科技引领未来投资之路
  • 鸿蒙next之axios二次封装并携带cookie
  • windows server 2008 建立ftp服务器
  • QT linux 打包时库和插件如何生成
  • 嵌入式浏览器 -- Chromium VS Firefox
  • 国内对接使用GPT解决方案——API中转
  • map的使用(c++)
  • 基于langchain框架的智能PDF问答(一)创建向量数据库
  • 全新更新!Fastreport.NET 2025.1版本发布,提升报告开发体验
  • ubuntu编译ffmpeg
  • 【mysql】导出导入mysql表结构或者数据
  • GPT避坑指南:如何辨别逆向、AZ、OpenAI官转
  • 使用阿里云 MQTT 服务进行消息传输的基本实践
  • 基于QT用工厂模式实现串口通信与网络通信激光器的控制
  • miRNA分析流程学习(四)/miRNA芯片数据差异分析再学习以及异常火山图可能原因解释
  • 【TEST】负载/性能测试工具 Grafana K6 (Docker 版)
  • 【系统架构设计师】案例分析预测试卷一(3道材料题)
  • 小满OKKICRM与钉钉数据集成方案解析
  • 扶贫工作数字化:SpringBoot精准扶贫系统
  • Python实现的简单时钟
  • 探索自动化数据清洗技术的前沿趋势
  • java项目使用HttpServletRequest request接参,怎么获取参数的值,怎么获取form值,怎么获取body值