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];
    }
};