给出两个单词 word1 和 word2，计算出将 word1 转换为 word2 的最少操作次数。 你总共三种操作方法：

• 插入一个字符
• 删除一个字符
• 替换一个字符

在线评测地址

样例 1:

输入:  "horse" "ros" 输出: 3 解释:  horse -> rorse (替换 'h' 为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e') 

样例 2:

输入:  "intention" "execution" 输出: 5 解释:  intention -> inention (删除 't') inention -> enention (替换 'i' 为 'e') enention -> exention (替换 'n' 为 'x') exention -> exection (替换 'n' 为 'c') exection -> execution (插入 'u') 

算法：DP

经典的二维 dp 。 定义 f[i][j]为 word1 前 i 个字符到 word2 的前 j 个字符的转化的最小步。 接着，我们来考虑状态转移方程。

• 假设对于 f[i][j]以前的之都已知，考虑 fi 的情形。
• 若 word1[i] = word2[j]，那么说明只要 word1 的前 i-1 个能转换到 word2 的前 j-1 个即可，所以 f[i][j] = f[i-1][j-1]
• 反之，若不等，我们就要考虑以下情形了。
• 给 word1 插入一个和 word2 最后的字母相同的字母，这时 word1 和 word2 的最后一个字母就一样了，此时编辑距离等于 1 （插入操作） + 插入前的 word1 到 word2 去掉最后一个字母后的编辑距离 f[i][j – 1] + 1
• 删除 word1 的最后一个字母，此时编辑距离等于 1 （删除操作） + word1 去掉最后一个字母到 word2 的编辑距离 f[i – 1][j] + 1
• 把 word1 的最后一个字母替换成 word2 的最后一个字母，此时编辑距离等于 1 （替换操作） + word1 和 word2 去掉最后一个字母的编辑距离。为 f[i – 1][j – 1] + 1
• 三者取最小值即可。

复杂度分析

• 时间复杂度 O(n^2)
  • 二维 dp
• 空间复杂度 O(n^2)
  • 需要保存二维的状态数

public class Solution {     public int minDistance(String word1, String word2) {         int n = word1.length();         int m = word2.length();          int[][] dp = new int[n+1][m+1];         for (int i = 0; i < m + 1; i++) {             dp[0][i] = i;          }          for (int i = 0; i < n + 1; i++) {             dp[i][0] = i;         }          for (int i = 1; i < n + 1; i++) {             for (int j = 1; j < m + 1; j++) {                 if (word1.charAt(i - 1) == word2.charAt(j - 1)) {                     dp[i][j] = dp[i - 1][j - 1];                 }else{                     dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]));                 }             }         }         return dp[n][m];     } } 

大佬有話說 (0)