动态规划 72. 编辑距离
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
示例 1：
代码语言：javascript复制输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')示例 2：
代码语言：javascript复制输入：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 由小写英文字母组成
代码
代码语言：javascript复制package ski.mashiro.leetcode;
public class _72 {
/**
* 72. 编辑距离
* <p>
* 给你两个单词 word1 和 word2, 请返回将 word1 转换成 word2 所使用的最少操作数。
* 你可以对一个单词进行如下三种操作：
* - 插入一个字符
* - 删除一个字符
* - 替换一个字符
*/
public static void main(String[] args) {
String str1 = "horse";
String str2 = "ros";
System.out.println(minDistance(str1, str2));
}
/**
* 自底而上的动态规划
*/
public static int minDistance(String word1, String word2) {
// 存放 word1 中 0..i 的子串 转换成 word2 中 0..j 的子串 所需的操作数
int[][] dp = new int[word1.length() 1][word2.length() 1];
for (int i = 1; i < word1.length() 1; i ) {
dp[i][0] = i;
}
for (int i = 1; i < word2.length() 1; i ) {
dp[0][i] = i;
}
for (int i = 1; i < word1.length() 1; i ) {
for (int j = 1; j < word2.length() 1; j ) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
// 对应字符如果相等，则不需要进行操作，复制上一层的操作数
dp[i][j] = dp[i - 1][j - 1];
} else {
// 取 增删改 操作的最小数，在此基础上增加本次的操作数 1
// dp[i - 1][j] word1 删除最后一个
// dp[i][j - 1] word2 删除最后一个 即 word1 增加一个
// dp[i][j] word1 word2 同时删除最后一个
dp[i][j] = 1 Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]);
}
}
}
return dp[word1.length()][word2.length()];
}
/**
* 自顶而下的递归
*/
public static int minDistance2(String word1, String word2) {
if (word1.length() == 0 || word2.length() == 0) {
return word1.length() word2.length();
}
if (word1.charAt(word1.length() - 1) == word2.charAt(word2.length() - 1)) {
return minDistance(word1.substring(0, word1.length() - 1), word2.substring(0, word2.length() - 1));
}
return 1 Math.min(
Math.min(
minDistance(word1, word2.substring(0, word2.length() - 1)),
minDistance(word1.substring(0, word1.length() - 1), word2)
),
minDistance(word1.substring(0, word1.length() - 1), word2.substring(0, word2.length() - 1))
);
}
}
