【LeetCode热题100】【多维动态规划】编辑距离

叶茂林

发布于 2024-04-24 08:16:23

1030

发布于 2024-04-24 08:16:23

文章被收录于专栏：叶子的开发者社区叶子的开发者社区

题目链接：72. 编辑距离 - 力扣（LeetCode）

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数

你可以插入、删除、替换字符

定义dp[i][j]是将word1[0:i-1]转换成word2[0:j-1]所使用的最少操作数

如果word1[i-1]等于word2[j-1]，那么说明dp[i][j]=dp[i-1][j-1]，不需要操作，否则的话：

要么替换，需要将word1[0:i-2]转换成word2[0:j-2]，即dp[i][j]=dp[i-1][j-1]+1

要么插入，需要将word1[0:i-1]转换成word2[0:j-2]，即dp[i][j]=dp[i][j-1]+1

要么删除，需要将word1[0:i-2]转换成word2[0:j-1]，即dp[i][j]=dp[i-1][j]+1

取决于它们三个哪个最小，当然word中有一个为空的情况所需要的操作次数都是另一个的长度

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size(), n = word2.size();
        vector<vector<int> > dp(m + 1, vector<int>(n + 1));
        for (int i = 0; i <= m; ++i)dp[i][0] = i;
        for (int i = 0; i <= n; ++i)dp[0][i] = i;
        for (int i = 1; i <= m; ++i)
            for (int j = 1; j <= n; ++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][j - 1], dp[i - 1][j])) + 1;
        return dp[m][n];
    }
};

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2024-04-23，如有侵权请联系 cloudcommunity@tencent.com 删除

动态规划