72.编辑距离

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

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

示例 1：

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

Solution

dp的状态转移方程：

image-20240517204451699

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    // 主方法，计算将字符串 text1 转换为字符串 text2 所需的最小操作数
    public int minDistance(String text1, String text2) {
        // 将字符串转换为字符数组，方便访问每个字符
        char[] s = text1.toCharArray(), t = text2.toCharArray();
        int n = s.length, m = t.length; // 获取两个字符串的长度
        // 初始化二维数组 f，大小为 (n+1) x (m+1)
        int[][] f = new int[n + 1][m + 1];

        // 初始化第一行，第一列
        for (int j = 0; j <= m; ++j) f[0][j] = j;
        for (int i = 0; i <= n; ++i) f[i][0] = i;
        // 遍历第一个字符串的每个字符
        for (int i = 0; i < n; ++i) {
            // 遍历第二个字符串的每个字符
            for (int j = 0; j < m; ++j) {
                // 如果当前字符相等，不需要额外操作，直接继承 f[i][j]
                if (s[i] == t[j]) {
                    f[i + 1][j + 1] = f[i][j];
                } else {
                    // 否则，取插入、删除、替换三种操作的最小值加 1
                    f[i + 1][j + 1] = Math.min(Math.min(f[i][j + 1], f[i + 1][j]), f[i][j]) + 1;
                }
            }
        }

        // 返回将 text1 转换为 text2 的最小操作数，即 f[n][m]
        return f[n][m];
    }
}

可以用一维dp数组来代替

在没有空间优化的版本里f[0] = list(range(m + 1))

也就是说最左边一列的值，自上而下分别为0 1 2 3 4 5 6 … 但优化成一个数组之后，最左边的那个值就需要自己手动累加了，否则一直都是0，那么“由短补长”或“由长补短”这两种情形内，必有一个答案是错的，要么是多出来的长度没计算删掉，要么是多出来的长度没计算补上f[0] += 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    // 主方法，计算将字符串 text1 转换为字符串 text2 所需的最小操作数
    public int minDistance(String text1, String text2) {
        char[] t = text2.toCharArray(); // 将 text2 转换为字符数组，方便访问每个字符
        int m = t.length; // 获取 text2 的长度
        int[] f = new int[m + 1]; // 初始化一维数组 f，大小为 m+1，用于存储动态规划的中间结果

        // 初始化 f 数组，表示将空字符串转换为 text2 的前 j 个字符所需的操作数
        for (int j = 1; j <= m; j++) f[j] = j;

        // 遍历第一个字符串 text1 的每个字符
        for (char x : text1.toCharArray()) {
            int pre = f[0]; // 保存上一个状态 f[j] 的值
            ++f[0]; // 更新 f[0]，表示将 text1 的前 i 个字符转换为空字符串所需的操作数

            // 遍历第二个字符串 text2 的每个字符
            for (int j = 0; j < m; ++j) {
                int tmp = f[j + 1]; // 保存当前状态 f[j + 1] 的值
                // 如果当前字符相等，不需要额外操作，直接继承 pre 的值
                // 否则，取插入、删除、替换三种操作的最小值加 1
                f[j + 1] = x == t[j] ? pre : Math.min(Math.min(f[j + 1], f[j]), pre) + 1;
                pre = tmp; // 更新 pre 为当前状态 f[j + 1] 的值，以便下次循环使用
            }
        }

        // 返回将 text1 转换为 text2 的最小操作数，即 f[m]
        return f[m];
    }
}