1. 题目
72. 编辑距离
2. 描述
给你两个单词 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’)
3. 实现方法
3.1 方法 1
3.1.1 思路
动态规划，分三步：
要求最少操作数，定义 dp[i][j] 为 字符串 word1 转换为 word2 所使用的的最少操作次数，其中 i 为 word1 长度，j 为 word2 长度；
找关系式：
将字符 word1[i] 替换为与 word2[j] 相等，dp[i] [j] = dp[i-1] [j-1] + 1;
在 word1 末尾插入与 word2[j] 相等的字符， dp[i] [j] = dp[i] [j-1] + 1;
删除字符 word1[i]，dp[i] [j] = dp[i-1] [j] + 1;
则有 dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
初始值，毫无疑问当我们的 i 或 j 任一为 0 时，不能再使用上述关系式，要将其中一个字符串转换为另一个字符串，此时只能一直进行插入或删除操作；
3.1.2 实现
public int minDistance(String word1, String word2) { int m = word1.length() + 1; int n = word2.length() + 1; if(n <= 0 || m <= 0){ return 0; } int[][] dp = new int[m][n]; // 最左列，即 word2 长度为 0 for(int i = 1; i < m; i++){ dp[i][0] = 1 + dp[i - 1][0]; } // 最上行，即 word1 长度为 0 for(int i = 1; i < n; i++){ dp[0][i] = 1 + dp[0][i - 1]; } // 求 dp[i][j] for(int i = 1; i < m; i++){ for(int j = 1; j < n; j++){ // 1. word1[i] == word2[j] if(word2.charAt(j - 1) == word1.charAt(i - 1)){ dp[i][j] = dp[i - 1][j - 1]; }else{ // 2. word1 替换后与 word2 相等 // 3. word1 插入后与 word2 相等 // 4. word1 删除后与 word2 相等 dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1; } } } return dp[m - 1][n - 1]; }
