每日一题：编辑距离

题目

给你两个单词 $a$ 和 $b$，请你计算出将 $a$ 转换成 $b$ 所使用的最少操作数。

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

1. 插入一个字符
2. 删除一个字符
3. 替换一个字符

Solution

$dp[i][j]$ 表示 $a$ 的前 $i$ 个字母和 $b$ 的前 $j$ 个字母匹配的最少操作次数。

可以从三种状态转移过来：

$dp[i][j] = dp[i - 1][j] + 1$ 在 $b[j]$ 后面插入一个字符 $a[i]$

$dp[i][j] = dp[i][j - 1] + 1$ 在 $a[i]$ 后面插入一个字符 $b[j]$

$dp[i][j] = dp[i - 1][j - 1] + (a[i - 1] != b[j - 1])$ 修改一个字符

选择最小的操作步数进行转移即可。

Code

class Solution {
public:
    int dp[1005][1005];
    int minDistance(string a, string b) {
        int n = a.size();
        int m = b.size();
        for (int i = 0; i <= n; i++)
            dp[i][0] = i;
        for (int i = 0; i <= m; i++)
            dp[0][i] = i;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                int x = dp[i - 1][j] + 1;   // 在 b[j] 后面插入一个字符 a[i]
                int y = dp[i][j - 1] + 1;   // 在 a[i] 后面插入一个字符 b[j]
                int z = dp[i - 1][j - 1] + (a[i - 1] != b[j - 1]);   // 修改一个字符
                dp[i][j] = min({x, y, z});
            }
        }
        return dp[n][m];
    }
};