LeetCode 72 —— 72.编辑间隔

标题

   72 编辑间隔
  给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操纵数 。
  你可以对一个单词进行如下三种操纵：
  

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

  提示：
  0 <= word1.length, word2.length <= 500
  word1 和 word2 由小写英文字母组成
  思绪

我一开始以为是，求最长公共子序列。 但是好像不是。
看看题解， 得到的dp方程是： “我们用 D[j] 表示 A 的前 i 个字母和 B 的前 j 个字母之间的编辑间隔。”
让我尝试明确一下，
比如 A 是 “horse”, B 是 “ros”,
首先是要比力一个空的字符串与一个非空的字符串，这也是我们的边界条件，这种情况下编辑间隔就黑白空字符串的长度。
比如 "" -> "abc"，那么编辑间隔就是 3。因为我们只需要增加三个字符即可。
我们列出这样的一个表格

1.       (B)j      0    1     2     3
2.                 ""   "r"   "ro"  "ros"
3.   (A) i     --------------------------
4. 0      ""   |   0    1     2     3
5. 1     "h"   |   1
6. 2    "ho"   |   2
7. 3   "hor"   |   3
8. 4  "hors"   |   4
9. 5 "horse"   |   5

复制代码

首先，D[0][0] 在这个例子中自然是 0。 因为 “” 和 “” 之间的编辑间隔是 1（一次替换）。
那么：

• 从 h -> r 需要 1 步， 进行替换即可。
  
• 从 ho -> r 需要 2 步， 先替换再删除或者先删除再替换都可以。
  
• 从 h -> ro 需要 2 步， 先替换再增加或者先增加再替换都可以。
  

我们就可以得到这个表格：

1.       (B)j      0    1     2     3
2.                 ""   "r"   "ro"  "ros"
3.   (A) i     --------------------------
4. 0      ""   |   0    1     2     3
5. 1     "h"   |   1    1     2
6. 2    "ho"   |   2    2
7. 3   "hor"   |   3
8. 4  "hors"   |   4
9. 5 "horse"   |   5

复制代码

接下来讨论 D[2][2], 也就是 ho -> ro 的编辑间隔。
从 ho -> ro，我们有三种路径，

• 从 ho -> r -> ro，ho -> r 的间隔为 2, 以是在这条路径上，ho -> ro 的间隔为 3
  
• 或者 ro -> h -> ho，ro -> h 的间隔为 2, 以是 在这条路径上，ro -> ho 的间隔为 3
  
• 另外我们其实可以用肉眼来看，ho -> ro 的间隔为 1，因为只需要替换 h 为 r 即可。
  

我们来想一下这种思维在矩阵中对应的含义，因为 ho和ro 都是以 o 末端，以是这个 o 是没故意义的。
那就意味着 ho -> ro 的间隔就是 h -> r 的间隔，也就是 1。
以上的三种路径中，我们取其最小值即可。
这个时间我们可以得到一个结论了：
如果 A[0...i] 和 B[0...j] 的最后一个字母相同，那么 D[j] = min( D[i-1][j] + 1, D[j-1] + 1, D[i-1][j-1] )
在这个例子中， ho -> ro = min(3, 3, 1) = 1
但是如果是"in" -> "ex"呢？也就是最后一个字母不相同的情况。
我们先列个表：

1.     (B)j        0     1     2
2.                 ""    "e"   "ex"
3.   (A) i     ---------------------
4. 0      ""   |   0     1     2
5. 0     "i"   |   1     1     2
6. 1    "in"   |   2     2

复制代码

从 in -> ex, 我们也有三种路径：

• in -> e -> ex，因为 in -> e 的间隔为 2, 以是 in -> ex 的间隔为 3
  
• ex -> i -> in，因为 ex -> i 的间隔为 2, 以是 ex -> in 的间隔为 3
  

上面这两种方案都是先删除，再替换，再增加，都是绕远路的办法。
但是现实上，我们可以直接替换 n 为 x，替换 i 为 e，这样就可以得到最短路径 = 2。
我们再来思考其背后的含义，其实也很简朴：
我们只看最后一个字母，就是 n -> x，我们直接将其替换就可以了。
这个时间前面的 i -> e, 也直接替换就可以了，以是其间隔就是这两次替换，也就是 2。
也就是说, 在这种路径下，D[j] = D[i-1][j-1] + 1
综合上面的来看，我们可以得到一个结论：
如果 A[0...i] 和 B[0...j] 的最后一个字母不同，那么

1. D[i][j] = min(
2.     D[i-1][j] + 1,  // 删除 A 的最后一个字母
3.     D[i][j-1] + 1,  // 删除 B 的最后一个字母
4.     D[i-1][j-1] + 1 // 替换 A 的最后一个字母为 B 的最后一个字母
5. )

复制代码

这样我们就得到了一个完备的 dp 方程。
最后我们只需要返回 D[m][n] 即可。
代码：

1. public class Q0072 {
3.     @Test
4.     public void test() {
5.         String word1 = "horse";
6.         String word2 = "ros";
7.         System.out.println(minDistance(word1, word2));
8.     }
10.     public int minDistance(String word1, String word2) {
11.         int m = word1.length();
12.         int n = word2.length();
14.         int[][] dp = new int[m + 1][n + 1];
15.         ArrayUtil.printArray(dp);
17.         // 边界情况
18.         for (int i = 1; i <= m; i++) {
19.             dp[i][0] = i;
20.         }
21.         for (int j = 0; j <= n; j++) {
22.             dp[0][j] = j;
23.         }
24.         ArrayUtil.printArray(dp);
26.         for (int i = 1; i <= m; i++) {
27.             for (int j = 1; j <= n; j++) {
28.                 System.out.println("i = " + i + ", j = " + j);
29.                 // A[0...i]
30.                 System.out.println("A[0...i] = " + word1.substring(0, i));
31.                 // B[0...j]
32.                 System.out.println("B[0...j] = " + word2.substring(0, j));
35.                 // 如果 A[0...i] 和 B[0...j] 的最后一个字母相同，那么 D[i][j] = min( D[i-1][j] + 1, D[i][j-1] + 1, D[i-1][j-1] )
36.                 if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
37.                     dp[i][j] = Math.min(Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1]);
38.                 } else {
39.                     // 如果 A[0...i] 和 B[0...j] 的最后一个字母不同，那么
40.                     // D[i][j] = min(
41.                     //    D[i-1][j] + 1,  // 删除 A 的最后一个字母
42.                     //    D[i][j-1] + 1,  // 删除 B 的最后一个字母
43.                     //    D[i-1][j-1] + 1 // 替换 A 的最后一个字母为 B 的最后一个字母
44.                     // )
45.                     dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
46.                 }
48.                 ArrayUtil.printArray(dp);
49.             }
50.         }
51.         return dp[m][n];
52.     }
53. }

复制代码

---

over~

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。