0072. 编辑距离

[utterances-bot]

0072. 编辑距离 | 算法通关手册

https://algo.itcharge.cn/solutions/0001-0099/edit-distance/

[S1mpleBug]

附C++代码

明确dp[i][j]的含义：word1的前i个元素和word2的前j个元素匹配的话，需要的操作数。

补充说明下，本题word1是不断改变的，所以不去讨论word2的相对增删会更易于理解，分为下面三种情况讨论：

• 初始化：
  • 当word1为空，word1要增加j个元素才能和word2匹配：dp[0][j] = j;
  • 当word2为空，word1要删除i个元素才能和word2匹配：dp[i][0] = i;
• word1[i-1] != word2[j-1]（i从0到i-1共i个元素）：
  • 将word1的第i位删除：dp[i][j] = dp[i-1][j] + 1;
  • 向word1的第i位插入：dp[i][j] = dp[i][j-1] + 1;
  • 对word1的第i位替换：dp[i][j] = dp[i-1][j-1] + 1;
• word1[i-1] == word2[j-1]：dp[i][j] == dp[i-1][j-1];

const int N = 5e2+10;
class Solution {
public:
    int minDistance(string word1, string word2) {
        int dp[N][N] = {0};
        int leni = word1.size();
        int lenj = word2.size();
        for(int i = 1; i <= leni; ++i) dp[i][0] = i;
        for(int j = 1; j <= lenj; ++j) dp[0][j] = j;
        for(int i = 1; i <= leni; ++i) {
            for(int j = 1; j <= lenj; ++j) {
                if(word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1];
                else dp[i][j] = min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1]))+1;
            }
        }
        return dp[leni][lenj];
    }
};