小学生都能看懂的题解 | #编辑距离(一)#

问题描述

我们有两个字符串，比如 "abc" 和 "ab"。我们想知道将 "abc" 变成 "ab" 需要多少次操作。可以做的操作有：

插入一个字符：比如将 "ab" 变成 "abc"，需要插入 'c'。
删除一个字符：比如将 "abc" 变成 "ab"，需要删除 'c'。
修改一个字符：比如将 "abc" 变成 "axc"，需要把 'b' 改成 'x'。

我们的目标是找出从一个字符串到另一个字符串的最少操作数。

解决方案步骤

我们使用一种叫 动态规划 的方法来解决这个问题。下面是我们要做的步骤：

创建一个表格：
- 我们用一个表格 dp 来存储每一步的结果。
- dp[i][j] 表示将 str1 的前 i 个字符变成 str2 的前 j 个字符所需要的最少操作数。
初始化表格：
- 如果 str1 是空的，那么我们需要插入 j 个字符才能变成 str2，所以 dp[0][j] = j。
- 如果 str2 是空的，那么我们需要删除 i 个字符才能变成空字符串，所以 dp[i][0] = i。
填充表格：
- 对于每一对字符，如果它们相等，就不需要操作，直接把上一个结果复制过来。
- 如果不相等，我们需要考虑三种操作（插入、删除和修改），并选取最少的操作数。
返回结果：
- 最后，dp[len(str1)][len(str2)] 就是从 str1 变到 str2 所需要的最少操作数。

代码实现

下面是 editDistance 方法的代码：

public int editDistance(String str1, String str2) {
    int m = str1.length();
    int n = str2.length();
    
    // 创建一个二维数组来存储操作数
    int[][] dp = new int[m + 1][n + 1];

    // 初始化第一列和第一行
    for (int i = 0; i <= m; i++) {
        dp[i][0] = i; // 从 str1 的前 i 个字符到空字符串需要 i 次删除
    }
    for (int j = 0; j <= n; j++) {
        dp[0][j] = j; // 从空字符串到 str2 的前 j 个字符需要 j 次插入
    }

    // 填充 dp 数组
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                // 如果字符相等，直接从左上角复制
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                // 如果字符不相等，取三种操作的最小值
                dp[i][j] = Math.min(Math.min(dp[i - 1][j] + 1, // 删除
                                               dp[i][j - 1] + 1), // 插入
                                               dp[i - 1][j - 1] + 1); // 修改
            }
        }
    }

    // 返回从 str1 到 str2 的最小操作数
    return dp[m][n];
}

代码解释

创建表格：
```
int[][] dp = new int[m + 1][n + 1];
```
- 这里我们创建了一个二维数组 dp，它的大小是 (m + 1) x (n + 1)。m 是 str1 的长度，n 是 str2 的长度。

初始化第一行和第一列：

for (int i = 0; i <= m; i++) {
    dp[i][0] = i; // 从 str1 的前 i 个字符到空字符串需要 i 次删除
}
for (int j = 0; j <= n; j++) {
    dp[0][j] = j; // 从空字符串到 str2 的前 j 个字符需要 j 次插入
}

我们设置第一行和第一列，表示将一个字符串变为空字符串所需的操作数。

填充表格：

for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
        if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
            dp[i][j] = dp[i - 1][j - 1]; // 字符相等
        } else {
            // 三种操作取最小值
            dp[i][j] = Math.min(Math.min(dp[i - 1][j] + 1, // 删除
                                            dp[i][j - 1] + 1), // 插入
                                            dp[i - 1][j - 1] + 1); // 修改
        }
    }
}

我们通过循环比较每对字符，并根据情况更新表格中的值。

返回结果：
```
return dp[m][n];
```
- 最后返回 dp[m][n] 的值，它表示将整个 str1 转换为 str2 所需的最少操作数。

示例解析

示例 1："nowcoder" 转换为 "new"：
- 修改 'o' 为 'e'，需要 1 次操作。
- 删除 'coder'，需要 5 次操作。
- 总共需要 6 次操作。
示例 2："intention" 转换为 "execution"：
- 可以逐个字符替换或插入，总共需要 5 次操作。
示例 3："now" 转换为 "nowcoder"：
- 需要添加 'c', 'o', 'd', 'e', 'r'，总共需要 5 次操作。