题目链接

编辑距离

题目描述

image.png

实现代码

动态规划思想：记dp[i][j]表示从word1前i个字符到word2的前j个字符的编辑距离，有两种情况：

  1. 当word1[i] == word2[j]时：dp[i][j] = dp[i-1][j-1]
  2. 当word1[i] ≠ word2[j]时：需要进行插入、删除或者替换操作，从三种操作的结果中取最小

三种操作的变换方式（变换的都是word1）：

  1. 插入：dp[i][j] = dp[i][j-1]
  2. 删除：dp[i][j] = dp[i-1][j]
  3. 替换：dp[i][j] = dp[i-1][j-1]

初始化条件：

  1. 对i = 0时，dp[i][j] = j
  2. 对j = 0时，dp[i][j] = i

实现代码：

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