leetcode 72. Edit Distance 编辑距离 (中等)
一、题目大意
标签: 动态规划
https://leetcode.cn/problems/edit-distance
给你两个单词 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 为止,和第二个字符串到位置 j 为止,最多需要几步编辑。当第 i 位和第 j 位对应的字符相同时,dp[i][j]等于 dp[i-1][j-1];当二者对应的字符不同时,修改的消耗是 dp[i-1][j-1]+1,插入 i 位置/删除 j 位置的消耗是 dp[i][j-1]+1,插入 j 位置/删除 i 位置消耗是 dp[i-1][j]+1。
三、解题方法
3.1 Java 实现
四、总结小记
2022/7/4 坚持每天一题
版权声明: 本文为 InfoQ 作者【okokabcd】的原创文章。
原文链接:【http://xie.infoq.cn/article/e974cfb26fcfff3e9bcb1f12d】。文章转载请联系作者。
评论