LeetCode72 编辑距离

发表于 | 分类于 |
字数统计: 268 | 阅读时长 ≈ 1

链接：https://leetcode-cn.com/problems/edit-distance/description/

题面

给定两个字符串，已知你可以删除、替换和插入任意字符串的任意字符，求最少编辑几步可以将两个字符串变成相同。

解法

比较经典的动态规划题目了
dp[i][j] 可以从 dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]转移而来
取决于第i个字符和第j个字符是否相等
记录一个自己的写法

代码

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
class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(),  n = word2.size();
        if (m == 0 || n == 0) {
            return max(m, n);
        }
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        // dp[i][j]表示s1前i个字符, s2前j个字符的最少编辑距离
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0) {
                    dp[i][j] = j;
                }
                else if (j == 0) {
                    dp[i][j] = i;
                }
                else {
                    int step = (word1[i - 1] != word2[j - 1]);
                    dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]) + 1, dp[i - 1][j - 1] + step);
                }
            }
        }
        return dp[m][n];
    }
};