首页 > 编程语言 >【算法题】72. 编辑距离-力扣(LeetCode)

【算法题】72. 编辑距离-力扣(LeetCode)

时间:2024-09-27 18:21:25浏览次数:10  
标签:len 替换 力扣 range word1 72 word2 LeetCode dp

【算法题】72. 编辑距离-力扣(LeetCode)

1.题目

下方是力扣官方题目的地址

72. 编辑距离

给你两个单词 word1word2请返回将 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
  • word1word2 由小写英文字母组成

2.题解

思路

本题看初看题目的增、删、改,会感觉非常困难,因为我们自己在利用例子模拟的时候都比较难。

但是我们不妨换个思路,利用动态规划的思想,将这个问题转换成一个个子问题,利用子问题的答案来得出最终答案。

我们定义dp数组dp[i,j]来代表word1i个字符变换到word2j个字符所需的最小操作次数。

定义完了之后,首先我们需要思考一些一些特殊的位置,比如说当i或j等于0时:

如果i0,我们就需要一直增,增的次数就是j,即word2当前的长度

如果j0,我们就需要一直删,删的次数就是i,即word1当前的长度

n,m=len(word1),len(word2)
dp=[[0]*(m+1) for _ in range(n+1)]
for i in range(n+1):
    dp[i][0]=i
for j in range(m+1):
    dp[0][j]=j
for i in range(1,n

处理完这些特殊位置之后,我们就可以考虑状态转移方程了

dp[i,j]是如何来的呢?

当然是通过前面增、删改来的

我们以word1 = "horse", word2 = "ros"为例,画出dp数组图:

在这里插入图片描述

所以我们模拟一下增、删、改的三种情况:

增:dp[i,j]=dp[i,j-1]+1

删:dp[i,j]=dp[i-1,j]+1

改:dp[i,j]=dp[i-1,j-1]+1

所以我们可以很容易地得出状态转移方程:

dp[i][j]=min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])+1

当然,如果当word1[i-1]==word2[j-1],即两个字符相同时,我们可以不进行任何增、删、改的操作,即:

dp[i][j]=dp[i-1][j-1]

考虑到这些,这个问题也就被解决了。

Python代码

class Solution(object):
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        n,m=len(word1),len(word2)
        dp=[[0]*(m+1) for _ in range(n+1)]      # 初始化dp数组
        for i in range(n+1):                    # 考虑特殊位置
            dp[i][0]=i
        for j in range(m+1):
            dp[0][j]=j
        for i in range(1,n+1):
            for j in range(1,m+1):
                    dp[i][j]=min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])+1    # 利用状态转移方程
                    if word1[i-1]==word2[j-1]:dp[i][j]=dp[i-1][j-1]       
        return dp[-1][-1]

3.结语

本人资历尚浅,发博客主要是记录与学习,欢迎大佬们批评指教!大家也可以在评论区多多交流,相互学习,共同成长。

标签:len,替换,力扣,range,word1,72,word2,LeetCode,dp
From: https://blog.csdn.net/Janium/article/details/142577660

相关文章

  • 8,(经典面试题:分组求topN)Python数分之Pandas训练,力扣,1532. 最近的三笔订单
    学习:知识的初次邂逅复习:知识的温故知新练习:知识的实践应用目录一,原题力扣链接二,题干三,建表语句四,分析五,Pandas解答六,验证七,知识点总结一,原题力扣链接.-力扣(LeetCode)二,题干表:Customers+---------------+---------+|ColumnName|Type|+------......
  • 26,【经典大厂面试题】【连续问题的困难题】Python数分之Pandas训练,力扣,2173. 最多连胜
    学习:知识的初次邂逅复习:知识的温故知新练习:知识的实践应用目录一,原题力扣链接二,题干三,建表语句四,分析五,SQL解答六,验证七,知识点总结一,原题力扣链接.-力扣(LeetCode)二,题干表: Matches+-------------+------+|ColumnName|Type|+-------------+-----......
  • 875. 爱吃香蕉的珂珂(leetcode)
    https://leetcode.cn/problems/koko-eating-bananas/description/二段性:速度有得完和不吃完两个段关键点是编写check函数,比较繁杂classSolution{publicintminEatingSpeed(int[]piles,inth){intsum=0;intmax=0;for(inti=0;i<piles.......
  • P10603 BZOJ4372 烁烁的游戏 题解
    题目传送门前置知识动态树分治|动态开点线段树|标记永久化解法考虑动态点分治。两种操作本质上是将luoguP6329【模板】点分树|震波的操作互换了下,将原需支持单点修改、区间查询的数据结构换成需支持区间修改、单点查询的数据结构即可。区间修改、单点查询的动态开......
  • Leetcode 154. 寻找旋转排序数组中的最小值 II
    1.题目基本信息1.1.题目描述已知一个长度为n的数组,预先按照升序排列,经由1到n次旋转后,得到输入数组。例如,原数组nums=[0,1,4,4,5,6,7]在变化后可能得到:若旋转4次,则可以得到[4,5,6,7,0,1,4]若旋转7次,则可以得到[0,1,4,4,5,6,7]注意,数组[a[0],a[1],a[2],......
  • 高性能双核 C66x 定点和浮点 DSP - TMS320C6672ACYPA25 TMS320C6672ACYP TMS320C6672A
    TMS320C6672DSP是一款基于TIKeyStone多核架构的高性能定点/浮点DSP。该器件集成了创新的C66xDSP内核,内核速度最高可达1.5GHz。对于各种应用程序的开发人员来说,例如关键任务系统、医学成像、测试和自动化,以及其他需要高性能的应用程序。这些DSP提供3GHz累积DSP,实现了一个高能......
  • 面试经典 150 题:力扣88. 合并两个有序数组
    每周一道算法题启动题目【题目链接】【解法一】合并后排序排序后的数组自动省略0的数字,又学到了classSolution{public:voidmerge(vector<int>&nums1,intm,vector<int>&nums2,intn){//合并两个数组后排序for(inti=0;i<n;i++)......
  • 【LeetCode Hot 100】21. 合并两个有序链表
    题目描述最简单粗暴的想法是将两个链表的所有元素拿出来放在一个数组中,再将此数组排序,最后生成一个新链表并返回。由于给出的参数本身就是两个排好序的链表,可以进行一次遍历,就能保证元素仍然是有序的:每次比较当前指针指向的两个元素的大小,较小的拿出来作为当前元素并将指针向前移......
  • 易优CMS出现:Allowed memory size of 134217728 bytes exhausted (tried to allocate 2
    当你遇到“Allowedmemorysizeof134217728bytesexhausted(triedtoallocate20480bytes)”的错误时,这意味着PHP的内存限制已经耗尽。这种错误通常发生在处理大量数据或执行复杂计算时。为了解决这个问题,可以采取以下几种方法:方法1:修改 php.ini 文件(推荐)找到 php......
  • 易优CMS登录后台报Allowed memory size of 134217728 bytes ex hausted (tried to alo
    当你在登录后台时遇到“Allowedmemorysizeof134217728bytesexhausted(triedtoallocate20480bytes)”的错误提示时,通常是由于PHP的内存限制不足导致的。以下是一些具体的解决步骤:步骤1:检查PHP配置登录宝塔面板登录宝塔面板。在左侧菜单栏选择“软件商店”。......