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’) 提示：

  • 0 <= word1.length, word2.length <= 500
  • word1 和 word2 由小写英文字母组成

解题思路

动态规划
经动态规划：编辑距离

解决两个字符串的动态规划问题，一般都是用两个指针i,j分别指向两个字符串的**最后**，然后一步步往前走，缩小问题的规模。
对于每对字符s1[i]和s2[j]，可以有四种操作：

  1. if s1[i] == s2[j]:
  2.     啥都别做（skip）
  3.     i, j 同时向前移动
  4. else:
  5.     三选一：
  6.         插入（insert）
  7.         删除（delete）
  8.         替换（replace）

1.暴力枚举

这个「三选一」到底该怎么选择呢？很简单，全试一遍，哪个操作最后得到的编辑距离最小，就选谁
base case:

  • 当j走完s2时，如果i还没走完s1，那么只能用删除操作把s1缩短为s2。
  • 如果i走完s1时j还没走完了s2，那就只能用插入操作把s2剩下的字符全部插入s1

image.png

2.备忘录优化

备忘录很好加，原来的代码稍加修改即可：

  1. def minDistance(s1, s2) -> int:
  2.     memo = dict() # 备忘录
  3.     def dp(i, j):
  4.         if (i, j) in memo: 
  5.             return memo[(i, j)]
  6.         ...
  7.         if s1[i] == s2[j]:
  8.             memo[(i, j)] = ...  
  9.         else:
  10.             memo[(i, j)] = ...
  11.         return memo[(i, j)]
  12.     return dp(len(s1) - 1, len(s2) - 1)

3.DP table优化

dp[i][j]的含义和之前的 dp 函数类似：

  • dp函数dp(i, j)返回 s1[0..i] 和 s2[0..j] 的最小编辑距离
  • dp[i][j]存储 s1[0..i-1] 和 s2[0..j-1]的最小编辑距离

dp 函数的 base case 是i,j等于 -1，而数组索引至少是 0，所以 dp 数组会偏移一位，dp[..][0]和dp[0][..]对应 base case。
既然 dp 数组和递归 dp 函数含义一样，也就可以直接套用之前的思路写代码，唯一不同的是，DP table 是自底向上求解，递归解法是自顶向下求解：
image.png

状态转移
72. 编辑距离 - 图3

  1. class Solution {
  2. public:
  3.     int minDistance(string word1, string word2) {
  4.         int m = word1.size(),n =  word2.size();
  5.         //dp[i][j]存储的是word1[0..i-1]和word2[0..j-1]的最小编辑距离
  6.         vector<vector<int>> dp(m+1,vector<int>(n+1));//创建二维数组
  7.         //base case
  8.         for (int i = 1; i <= m;i++) dp[i][0] = i;
  9.         for (int j = 1; j <= n;j++) dp[0][j] = j;
  10.         //自底向上求解
  11.         for (int i = 1;i <= m;i++) {
  12.             for (int j = 1;j <= n;j++) {
  13.                 if (word1[i-1] == word2[j-1])//两个字符相同，不需要做任何操作 
  14.                     dp[i][j] = dp[i-1][j-1];
  15.                 else {//插入，删除，替换
  16.                     dp[i][j] = mymin(dp[i][j-1] + 1,dp[i-1][j] + 1,dp[i-1][j-1] + 1);
  17.                 }
  18.             }
  19.         }
  20.         return dp[m][n];
  21.     }
  23.     int mymin(int a,int b,int c) {
  24.         return min(a,min(b,c));
  25.     }
  26. };