编辑距离(LeetCode-72)

简介: 编辑距离(LeetCode-72)

编辑距离(LeetCode-72)


题目

给你两个单词 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[i][j] 含义


将 i − 1 为结尾的字符串word1转换为 j − 1为结尾的字符串word2,最少操作数为 d p [ i ] [ j ]

递推公式

如果 w o r d 1 [ i − 1 ] = w o r d 2 [ j − 1 ]

不进行任何操作,值为 d p [ i − 1 ] [ j − 1 ]

如果二者不相等,有下述三种情况

首先要清楚word2添加一个元素,等价于word1删除一个元素!二者操作次数也均为一次!

操作一:word1删除一个元素,最少操作次数为 d p [ i − 1 ] [ j ] + 1

操作二:word2删除一个元素,最少操作次数为 d p [ i ] [ j − 1 ] + 1

操作三:word1替换一个元素,最少操作次数为 d p [ i − 1 ] [ j − 1 ] + 1 d

三者取最小值

数组初始化


dp[i][0] 明显等于 i

dp[0][j] 明显等于 j

遍历顺序


从前往后

测试用例



代码展示

class Solution
{
public:
    int minDistance(string word1, string word2)
    {
        int n1 = word1.size();
        int n2 = word2.size();
        vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1));
        for (int i = 1; i <= n1; i++)
        {
            dp[i][0] = i;
        }
        for (int j = 1; j <= n2; j++)
        {
            dp[0][j] = j;
        }
        for (int i = 1; i <= n1; i++)
        {
            for (int j = 1; j <= n2; j++)
            {
                if (word1[i - 1] == word2[j - 1])
                {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                else
                {
                    dp[i][j] = min({dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1});
                }
            }
        }
        return dp[n1][n2];
    }
};
目录
相关文章
|
Web App开发 数据采集 Java
【Python】已完美解决:selenium.common.exceptions.SessionNotCreatedException: Message: session not created
【Python】已完美解决:selenium.common.exceptions.SessionNotCreatedException: Message: session not created
1360 0
|
存储 数据库 数据安全/隐私保护
SpringSecurity6从入门到实战之登录表单的提交
SpringSecurity6 教程探讨了登录表单提交的源码流程。当提交登录表单时,`UsernamePasswordAuthenticationFilter` 负责处理认证,它从请求中获取 `username` 和 `password` 参数。然后,`AuthenticationManager` 的 `authenticate()` 方法被调用,进一步委托给 `AuthenticationProvider`,通常是 `DaoAuthenticationProvider`。`DaoAuthenticationProvider` 使用 `UserDetailsService`(如 `InMemo
|
域名解析 JavaScript 网络协议
技术心得记录:如何使用google地图的api(整理)
技术心得记录:如何使用google地图的api(整理)
1187 0
|
Docker 容器
搭建自己的Docker Harbor镜像仓库(1)--- 安装篇
搭建自己的Docker Harbor镜像仓库(1)--- 安装篇
276 1
|
机器学习/深度学习 编解码 数据挖掘
实例分割综述总结综合整理版
实例分割综述总结综合整理版
728 0
实例分割综述总结综合整理版
|
新零售 监控 供应链
【迪卡侬中国】人货“双轮驱动”下的数字化转型,支撑生意确定性增长
【迪卡侬中国】人货“双轮驱动”下的数字化转型,支撑生意确定性增长
806 0
|
机器学习/深度学习 Shell 计算机视觉
【论文精读】CVPR2021 - ReDet:一种用于航空目标检测的旋转等变检测器
【论文精读】CVPR2021 - ReDet:一种用于航空目标检测的旋转等变检测器
|
安全 Java Maven
MapStruct使用
MapStruct使用
|
缓存 Ruby Perl
重装Cocoapods遇到的问题
重装Cocoapods遇到的问题
重装Cocoapods遇到的问题
|
SQL 关系型数据库 MySQL
MySql 过滤查询(以字母开头,以数字开头,非数字开头,非字母开头)
我们知道,SQL Server中判断一个字段的值是否为数字可以用系统自带的ISNUMERIC()函数来处理,但是MySQL数据库中则没有这个(或者是没有一个直接判断是否是数字)的函数,但MySQL为我们提供了正则表达式的函数,所以我们可以用数字的正则表达式来处理有关判断字段值是否是数字的问题,具体的MySQL语句代码示例如下: SELECT * FROM TABLE_NAME WHERE COLUMN_NAME REGEXP '^[0-9]+$'
1490 1