【每日打卡】[leetcode]72-编辑距离

马谦马谦马谦
马谦马谦马谦
马谦马谦马谦
615
文章
12
评论
2020年4月6日23:46:13 评论

来源:力扣(LeetCode)

链接:https://leetcode-cn.com/problems/edit-distance

著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

一、题目描述

给你两个单词 word1 和 word2,请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作:

  1. 插入一个字符
  2. 删除一个字符
  3. 替换一个字符

示例 1:

  • 输入:word1 = "horse", word2 = "ros"
  • 输出:3
  • 解释:

示例 2:

  • 输入:word1 = "intention", word2 = "execution"
  • 输出:5
  • 解释:

【每日打卡】[leetcode]72-编辑距离

二、题目解析

这道题目和leetcode44-通配符匹配很类似,比较两个字符串之间的状态,因此也可以使用相同的办法。以dp[i][j]表示word1的第i个字符到word2的第j字符转换需要的最小操作数,动态转移方程可以表示为:
【每日打卡】[leetcode]72-编辑距离

说明:如果word1[i]和word2[j]相等,那么最小操作次数就等于dp[i-1][j-1]。如果不相等,那么操作次数就应该是两个字符串的前一个字符匹配结果中的最小值加一。

三、代码

 

马谦马谦马谦
  • 本文由 发表于 2020年4月6日23:46:13
  • 转载请务必保留本文链接:https://www.dyxmq.cn/program/algorithms/leetcode72-edit-distance.html
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: