Edit Distance

72. 编辑距离

分析

状态定义
- 设 f[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最少操作数。
状态转移
- 如果 word1[i] == word2[j]：不需要额外操作，状态继承自子问题：f[i][j] = f[i-1][j-1]
- 如果 word1[i] != word2[j]：需要进行操作，从以下三种操作中选择代价最小的一种：f[i][j] = min(f[i-1][j-1] + 1, f[i-1][j] + 1, f[i][j-1] + 1)
  - 替换：f[i-1][j-1] + 1
  - 删除：f[i-1][j] + 1
  - 插入：f[i][j-1] + 1
边界条件
- f[i][0] = i: 将 word1 的前 i 个字符转换为空字符串，需要删除 i 次
- f[0][j] = j: 将空字符串转换为 word2 的前 j 个字符，需要插入 j 次
初始化输入：
- 在代码中通过向 word1 和 word2 开头添加空格，统一了状态的表示
最终结果：
- 返回 f[n][m]，其中 n 是 word1 的长度， m 是 word2 的长度

时间复杂度

外层循环遍历 n，内层循环遍历 m，总时间复杂度为 O(nm)

空间复杂度

空间复杂度为 O(nm)

C++代码

 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
32
33


class Solution
{
public:
    int minDistance(string word1, string word2)
    {
        // 在字符串开头添加空格，便于边界处理
        word1 = " " + word1;
        word2 = " " + word2;
        int n = word1.size(), m = word2.size();

        std::vector<std::vector<int>> f(n, std::vector<int>(m));

        // 初始化边界条件
        for (int i = 0; i < n; ++i)
            f[i][0] = i;
        for (int j = 0; j < m; ++j)
            f[0][j] = j;

        for (int i = 1; i < n; ++i)
            for (int j = 1; j < m; ++j)
            {
                // 删除、插入、替换操作的最优选择
                f[i][j] = std::min(f[i - 1][j] + 1, f[i][j - 1] + 1);
                if (word1[i] == word2[j])
                    f[i][j] = std::min(f[i][j], f[i - 1][j - 1]);
                else
                    f[i][j] = std::min(f[i][j], f[i - 1][j - 1] + 1);
            }

        // 返回结果
        return f[n - 1][m - 1];
    }
};