【每日打卡】 [leetcode]72-编辑距离

马谦马谦马谦

615
文章

17
评论

2020 年 4 月 6 日 23:46:13数据结构和算法评论363字数 576阅读 1 分 55 秒阅读模式

来源：力扣（LeetCode）

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

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

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

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

示例 1：

输入：word1 = "horse", word2 = "ros"
输出：3
解释：

horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

horse -> rorse ( 将 'h' 替换为 'r')

rorse -> rose ( 删除 'r')

rose -> ros ( 删除 'e')

示例 2：

输入：word1 = "intention", word2 = "execution"
输出：5
解释：

intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

intention -> inention ( 删除 't')

inention -> enention ( 将 'i' 替换为 'e')

enention -> exention ( 将 'n' 替换为 'x')

exention -> exection ( 将 'n' 替换为 'c')

exection -> execution ( 插入 'u')

【每日打卡】[leetcode]72-编辑距离-图片1

二、题目解析

这道题目和 leetcode44-通配符匹配很类似，比较两个字符串之间的状态，因此也可以使用相同的办法。以 dp[i][j]表示 word1 的第 i 个字符到 word2 的第 j 字符转换需要的最小操作数，动态转移方程可以表示为：

说明：如果 word1[i] 和 word2[j] 相等，那么最小操作次数就等于 dp[i-1][j-1]。如果不相等，那么操作次数就应该是两个字符串的前一个字符匹配结果中的最小值加一。

三、代码

static inline int min(int x, int y) {
    return x < y ? x : y;
}

class Solution {
public:
    int minDistance(string word1, string word2) {
        int i, j, row, col;
        vector<vector<int>> dp;

        if (word1.empty() || word2.empty())
            return word1.size() + word2.size();

        row = word1.size();
        col = word2.size();
        dp.reserve(row + 1);

        for (i = 0; i <= row; i++) {
            dp.emplace_back();
            vector<int> &v = dp[i];
            dp[i].reserve(col + 1);
            for (j = 0; j <= col; j++) {
                if (j == 0) {
                    dp[i].push_back(i);
                } else if (i == 0) {
                    dp[i].push_back(j);
                } else {
                    dp[i].push_back(0);
                }
            }
        }

        for (i = 1; i <= word1.size(); i++) {
            for (j = 1; j <= word2.size(); j++) {
                if (word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                }
            }
        }
        return dp[row][col];
    }
};