72.编辑距离

题目描述

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

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

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

示例 1：

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
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')

解题思路

1. 确定dp数组的含义 dp[i][j]: 以i-1结尾的world1, 和以j-1结尾的world2, 最近编辑距离为dp[i][j]

2. 递推公式

• word1[i-1]与world2[j-1]相等时: 不操作

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

• word1[i-1]与world2[j-1]不相等时

  • word1删除一个元素: dp[i][j] = dp[i-1][j] + 1
  • word2删除一个元素：dp[i][j] = dp[i][j-1] + 1 word1添加一个元素，相当于word2删除一个元素，因此没有元素增加操作
  • word1替换word[i-1]，使其与word2[j-1]相同: dp[i][j] = dp[i-1][j-1] + 1 dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])+1

3. dp数组初始化 dp[i][0]: word2为空字符串，以i-1结尾的字符串word1需要删除i个元素才能和word2相同, dp[i][0]=i dp[0][j]: 同理, dp[0][j]=j
4. 确定遍历顺序 从上到下，从左到右
5. 打印dp数组

代码实现

核心模式

class Solution{
    public:
    int minDistance(string word1, string word2){
        vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));

        // initialize the DP array
        for (int i = 0; i <= word1.size(); i++){
            dp[i][0] = i;
        }
        for (int j = 0; j <= word2.size(); j++){
            dp[0][j] = j;
        }
        
        // traversal
        for (int i = 1; i <= word1.size(); i++){
            for (int 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] = std::min(dp[i - 1][j - 1] + 1, std::min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
                }
            }
        }
        return dp[word1.size()][word2.size()];
    }
};

ACM模式

"dynamicPro.h"

#include <iostream>
#include "dynamicPro.h"

class Solution{
    public:
    int minDistance(string word1, string word2){
        vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));

        // initialize the DP array
        for (int i = 0; i <= word1.size(); i++){
            dp[i][0] = i;
        }
        for (int j = 0; j <= word2.size(); j++){
            dp[0][j] = j;
        }
        
        // traversal
        for (int i = 1; i <= word1.size(); i++){
            for (int 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] = std::min(dp[i - 1][j - 1] + 1, std::min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
                }
            }
        }
        print2DVector(dp);
        return dp[word1.size()][word2.size()];
    }
};

int main(){
    Solution solution;
    cout << "Result1's DP array = " << solution.minDistance("horse", "ros") << endl;
    cout << "Result2's DP array = " << solution.minDistance("intention", "execution") << endl;

    return 0;
}

• 输出

Result1's DP array = [[0, 1, 2, 3], [1, 1, 2, 3], [2, 2, 1, 2], [3, 2, 2, 2], [4, 3, 3, 2], [5, 4, 4, 3]]
3
Result2's DP array = [[0, 1, 2, 3, 4, 5, 6, 7, 8, 9], [1, 1, 2, 3, 4, 5, 6, 6, 7, 8], [2, 2, 2, 3, 4, 5, 6, 7, 7, 7], [3, 3, 3, 3, 4, 5, 5, 6, 7, 8], [4, 3, 4, 3, 4, 5, 6, 6, 7, 8], [5, 4, 4, 4, 4, 5, 6, 7, 7, 7], [6, 5, 5, 5, 5, 5, 5, 6, 7, 8], [7, 6, 6, 6, 6, 6, 6, 5, 6, 7], [8, 7, 7, 7, 7, 7, 7, 6, 5, 6], [9, 8, 8, 8, 8, 8, 8, 7, 6, 5]]
5