LeetCode #72:Edit Distance(编辑距离)

题目描述

有了 #583 的铺垫,本题相对来说就容易一些了。本题只有状态转移方程和 #583 不一样,其它完全一致。

状态定义:设 dp[i][j] 为字符串 word1[0…i-1],和字符串 word2[0…j-1],想要达到相等,所需要操作的最少次数。

dp[i][j] 的转移有两种情况:

① 当 word1[i-1] == word2[j-1] 时,即两个串末尾相等时,不需要进行任何操作,将问题转化为操作 word1[0…i-2] 与 word2[0…j-2] 中的字符,其状态转移方程为:

dp[i][j] = dp[i-1][j-1];

② 当 word1[i-1] != word2[j-1] 时,我们可以尝试删除 word1[i-1]、删除 word2[j-1]、替换 word1[i-1],使其与 word2[j-1] 相等(也可看作替换 word2[j-1],使其与 word1[i-1] 相等)。这三种情况需要取最小值,状态转移方程为:

dp[i][j] = min(dp[i][j - 1] + 1, dp[i - 1][j] + 1, dp[i - 1][j - 1] + 1);

添加元素去哪了呢?其实 word1 删除一个元素,就等价于 word2 添加一个元素,反之亦然。

dp 数组初始化与 #583 完全一致。

代码实现如下:

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.length();
        int m = word2.length();

        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        dp[0][0] = 0;
        for(int i = 1; i <= n; i ++)
            dp[i][0] = i;
        
        for(int j = 1; j <= m; j ++) 
            dp[0][j] = j;

        for(int i = 1; i <= n; i ++) {
            for(int j = 1; j <= m; j ++) {
                if(word1[i - 1] == word2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1];
                else
                    dp[i][j] = min(dp[i][j - 1] + 1, min(dp[i - 1][j] + 1, dp[i - 1][j - 1] + 1)); // 与#583唯一的区别就在这一行
            }
        }

        return dp[n][m];
    }
};

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注