【算法题】72. 编辑距离-力扣(LeetCode)
1.题目
下方是力扣官方题目的地址
给你两个单词 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
由小写英文字母组成
2.题解
思路
本题看初看题目的增、删、改,会感觉非常困难,因为我们自己在利用例子模拟的时候都比较难。
但是我们不妨换个思路,利用动态规划的思想,将这个问题转换成一个个子问题,利用子问题的答案来得出最终答案。
我们定义dp数组dp[i,j]
来代表word1
前i
个字符变换到word2
前j
个字符所需的最小操作次数。
定义完了之后,首先我们需要思考一些一些特殊的位置,比如说当i
或j等于0
时:
如果i
为0
,我们就需要一直增,增的次数就是j
,即word2
当前的长度
如果j
为0
,我们就需要一直删,删的次数就是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