题解 | #计算字符串的编辑距离#

#include <iostream>
using namespace std;
#include <string>
#include <vector>
int main() {
    string str1, str2;
    getline(cin, str1);
    getline(cin, str2);
    vector<vector<int>> dp (str1.size()+1, vector<int>(str2.size()+1, 0));
    for (int i = 0; i <=str1.size(); i++) {
        dp[i][0] = i;
    }
    for (int j = 0; j <= str2.size(); j++) {
        dp[0][j] = j;
    }

    for(int i = 1; i <=str1.size();i++){
        for(int j = 1; j <=str2.size();j++){
            if(str1[i-1] == str2[j-1]){
                dp[i][j] = dp[i-1][j-1];
            }
            else{
                int num1 = dp[i-1][j] + 1;
                int num2 = dp[i][j-1] + 1;
                int num3 = dp[i-1][j-1] + 1;
                dp[i][j] = min(num1,num2);
                dp[i][j] = min(num3,dp[i][j]);
            }
        }
    }
    cout << dp[str1.size()][str2.size()] << endl;
}

附上笔记

2.4 编辑距离

2.4.1 问题描述

• 给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。 可以单词进行插入/删除/替换1个字符的操作最少操作数可以在2个词中分别操作，但是其实结果都是一样的

2.4.2 dp数组含义

• dp[i][j]以i-1为尾word1和以j-1为结尾的字符串word2,最近编辑距离为dp[i][j]

2.3.4 递推公式

• if(word1[i-1] == word[j-1]) dp[i][j] = dp[i-1][j-1]
• else dp[i][j] = min( dp[i-1][j] + 1 或 dp[i][j-1] +1//删除word1[i-1]/添加在word2，增删本质一体dp[i-1][j-1]+1//替换一个元素

2.3.5 初始化

• dp[i][0] = i;
• dp[0][j] = j;

2.3.6 遍历顺序

• 从左到右，从上到下