LeetCode072之编辑距离(相关话题:动态规划)
规划 动态 相关 编辑 距离 话题
2023-09-11 14:20:00 时间
题目描述:
给你两个单词 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')
解题思路:
对单词 A 删除一个字符和对单词 B 插入一个字符是等价的。
同理,对单词 B 删除一个字符和对单词 A 插入一个字符也是等价的&#
相关文章
- 【荐】如何规划 Nginx 网站目录的权限(用户,用户组,ssh,sftp)
- Java实现 LeetCode 740 删除与获得点数(递推 || 动态规划?打家劫舍Ⅳ)
- [usaco]5.3.2 Milk Measuring 动态规划
- Leetcode 专项刷题题解---- 动态规划
- 数学建模学习笔记(二十四)多目标规划
- 联想高级架构师分享:架构之道-规划、简化和演化
- atitit uke企业行政部 世界行政区域划分表 与邮政编码规划 v5 r88.xlsx
- atitit.短信 验证码 破解 v3 p34 识别 绕过 系统方案规划----业务相关方案 手机验证码 .doc
- 【【henuacm2016级暑期训练】动态规划专题 N】Valid Sets
- 【 【henuacm2016级暑期训练】动态规划专题 K】 Really Big Numbers
- 【无人机】基于灰狼优化算法的无人机路径规划问题研究(Matlab代码实现)
- 剑指 Offer 63. 股票的最大利润-动态规划算法
- 剑指 Offer II 104. 排列的数目-动态规划算法
- 915. 分割数组-动态规划算法
- 583. 两个字符串的删除操作-动态规划
- 动态规划-hdoj-4832-百度之星2014初赛第二场
- 建模算法(四)——动态规划
- LeetCode动态规划的解题思路
- 机器人控制算法八之路径规划算法:RRT、RRT-Connect、Dynamic-Domain RRTs*
- 一文解析动态规划中的背包问题