题目描述

给你两个单词 word1 和 word2 ，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：

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

    来源，leetcode 每日一题 72. 编辑距离

例如：

  1. 输入：word1 = "horse", word2 = "ros"
  2. 输出：3
  3. 解释：
  4. horse -> rorse (将 'h' 替换为 'r')
  5. rorse -> rose (删除 'r')
  6. rose -> ros (删除 'e')

示例2：

  1. 输入：word1 = "intention", word2 = "execution"
  2. 输出：5
  3. 解释：
  4. intention -> inention (删除 't')
  5. inention -> enention (将 'i' 替换为 'e')
  6. enention -> exention (将 'n' 替换为 'x')
  7. exention -> exection (将 'n' 替换为 'c')
  8. exection -> execution (插入 'u')

解题思路

  1. 暴力求解，将所有的可能性都求出来，取一个最小的，指数爆炸
  2. 降低复杂度，求解子问题，子问题就是，如果 word1 转换到 72. 编辑距离 - 图1需要k步，则 word2_i 到 word2 只需要k+1步。

    更详细的思路，请参考：https://leetcode-cn.com/problems/edit-distance/solution/bian-ji-ju-chi-by-leetcode-solution/

代码

  1. class Solution {
  2. public:
  3.     int minDistance(string word1, string word2) {
  4.         int n = word1.length();
  5.         int m = word2.length();
  7.         // 有一个字符串为空串
  8.         if (n * m == 0) return n + m;
  10.         // DP 数组
  11.         int D[n + 1][m + 1];
  13.         // 边界状态初始化
  14.         for (int i = 0; i < n + 1; i++) {
  15.             D[i][0] = i;
  16.         }
  17.         for (int j = 0; j < m + 1; j++) {
  18.             D[0][j] = j;
  19.         }
  21.         // 计算所有 DP 值
  22.         for (int i = 1; i < n + 1; i++) {
  23.             for (int j = 1; j < m + 1; j++) {
  24.                 int left = D[i - 1][j] + 1;
  25.                 int down = D[i][j - 1] + 1;
  26.                 int left_down = D[i - 1][j - 1];
  27.                 if (word1[i - 1] != word2[j - 1]) left_down += 1;
  28.                 D[i][j] = min(left, min(down, left_down));
  30.             }
  31.         }
  32.         return D[n][m];
  33.     }
  34. };