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

LeetCode72:编辑距离

题目链接:72. 编辑距离 - 力扣(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] + 1);
                }
            }
        }

        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] + 1);
}

在这个之前我们先知道,如果word1删除一个元素,是不是和word2添加一个元素的效果是一样的。

如果word1[i - 1]等于word2[i - 1]的话,word1删除,也就是dp[i - 1][j] + 1,然后就是word1添加元素,其实word1添加元素,那么是不是和word2删除元素是一样的,这个时候那么我们就直接转换成dp[i][j - 1] + 1就可以了,因为dp的j列其实也就是word2字符串长度的大小。在一个就是替换,这个替换的话,就需要dp[i - 1][j - 1] + 1,因为替换完变成一样的了,那么就需要再加一步操作就好,这个时候的长度是不会改变的。然后取最小的值就好。

初始化:

这个时候我们需要初始化这两个dp[i][0]和dp[0][j],这个就需要数值了,因为需要初始化数值才能往后进行推到

遍历顺序:

这个题目还是一样,由左到右,由上到下就可以了,所以这个题目我们就正常遍历就好了。

返回值:这个我们返回的仍然是两个字符串的长度即可。


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

相关文章:

  • 鸿蒙next之axios二次封装并携带cookie
  • 【04】RabbitMQ的集群机制
  • STM32外设应用
  • 钉钉与金蝶云星空数据集成:提高企业付款申请单处理效率
  • 量化交易打怪升级全攻略
  • 着色器的认识
  • javaScript中复制一个数组的浅拷贝和深拷贝方法
  • Flutter Web部署到子路径的打包指令
  • 单细胞数据分析(四):细胞亚型注释
  • uniapp写抖音小程序阻止右滑返回上一个页面
  • Vue3使用AntV | X6绘制流程图:开箱即用
  • MPSK(BPSK/QPSK/8PSK)调制解调的Matlab仿真全套
  • TensorFlow面试整理-分布式
  • C语言——linux编程(上)
  • Fsm1
  • 枫清科技仲光庆:AI+行业新范式,双轮驱动助力数智化升级
  • 沪深A股上市公司数据报告分析
  • [蓝桥杯 2018 省 B] 乘积最大-题解
  • 配置mysql 主主模式 GTID
  • SpringBoot篇(运维实用篇 - 日志)
  • CentOS 系统刷新 DNS,解析
  • Visual Studio 字符集设置与文件编码的区别
  • 学习力体系
  • 【Python】爬虫程序打包成exe
  • Markdown 链接
  • view design之table自定义单元格模版