LeetCode热题100--72. 编辑距离--中等

题目

给你两个单词 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’)

题解

classSolution{publicintminDistance(Stringword1,Stringword2){intn1=word1.length();intn2=word2.length();int[][]dp=newint[n1+1][n2+1];// 第一行for(intj=1;j<=n2;j++)dp[0][j]=dp[0][j-1]+1;// 第一列for(inti=1;i<=n1;i++)dp[i][0]=dp[i-1][0]+1;for(inti=1;i<=n1;i++){for(intj=1;j<=n2;j++){if(word1.charAt(i-1)==word2.charAt(j-1))dp[i][j]=dp[i-1][j-1];elsedp[i][j]=Math.min(Math.min(dp[i-1][j-1],dp[i][j-1]),dp[i-1][j])+1;}}returndp[n1][n2];}}

解析

出自：自底向上和自顶向下

classSolution{publicintminDistance(Stringword1,Stringword2){// 获取 word1 的长度，记为 n1intn1=word1.length();// 获取 word2 的长度，记为 n2intn2=word2.length();// 创建二维 DP 表 dp，大小为 (n1+1) x (n2+1)// dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最小操作数int[][]dp=newint[n1+1][n2+1];// 初始化第一行：dp[0][j] 表示将空字符串 "" 转换为 word2 的前 j 个字符// 只能通过连续插入 j 次实现，所以 dp[0][j] = jfor(intj=1;j<=n2;j++)dp[0][j]=dp[0][j-1]+1;// 初始化第一列：dp[i][0] 表示将 word1 的前 i 个字符转换为空字符串 ""// 只能通过连续删除 i 次实现，所以 dp[i][0] = ifor(inti=1;i<=n1;i++)dp[i][0]=dp[i-1][0]+1;// 填充 DP 表的其余部分（从 i=1 到 n1，j=1 到 n2）for(inti=1;i<=n1;i++){for(intj=1;j<=n2;j++){// 如果当前字符相同（word1[i-1] == word2[j-1]），则不需要操作，// 直接继承左上角的值：dp[i][j] = dp[i-1][j-1]if(word1.charAt(i-1)==word2.charAt(j-1))dp[i][j]=dp[i-1][j-1];else// 如果字符不同，则考虑三种操作中的最小代价：// 1. 替换：dp[i-1][j-1] + 1 （把 word1[i-1] 改成 word2[j-1]）// 2. 插入：dp[i][j-1] + 1 （在 word1 后插入 word2[j-1]）// 3. 删除：dp[i-1][j] + 1 （删除 word1[i-1]）// 取三者最小值，并加 1（表示执行一次操作）dp[i][j]=Math.min(Math.min(dp[i-1][j-1],// 替换dp[i][j-1]),// 插入dp[i-1][j]// 删除)+1;}}// 返回最终结果：将整个 word1 转换为整个 word2 所需的最小操作数returndp[n1][n2];}}