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

#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>
using namespace std;

int main() {
    string str1, str2;
    cin >> str1 >> str2;
    int size1 = str1.size();
    int size2 = str2.size();
    
    int max_size = max(size1, size2);

    // dp[i][j]表示str1的0~i-1和str2的0~j-1的编辑距离 dp[0]表示空字符串 dp[1]表示字符串中的第一个字符 也就是在字符串中下表为0的字符
    vector<vector<int> > dp(size1 + 1, vector<int>(size2 + 1, INT_MAX)); 

    dp[0][0] = 0;
    //编辑距离初始化
    for(int i = 1; i <= size1; ++i) dp[i][0] = i;
    for(int j = 1; j <= size2; ++j) dp[0][j] = j;

    for(int i = 1; i <= size1; ++i) {
        for(int j = 1; j <= size2; ++j) {
            if(str1[i - 1] == str2[j - 1]) { //第i个等于第j个时
                dp[i][j] = dp[i-1][j-1];
            } else {
                 dp[i][j] = 1 + min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});
            }
        }
    }
    cout << dp[size1][size2] << endl;
    return 0;
}

着重解释下为什么递推式为dp[i][j] = 1 + min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});

分为五种情况：(+1都自动略去)

一、str1删除元素str[i-1]，此时就是str1的前i-1个元素和str2的前j个元素进行编辑距离计算，即dp[i-1][j]

二、str1增加元素 让其最新元素等于str2[j-1]，此时就是str1的前i+1个元素与str2的前j个元素进行编辑距离计算，即dp[i+1][j]，但是由于str1刚刚新加的元素等于str2[j-1]，即str1[i] == str2[j-1]，因此dp[i+1][j] == dp[i][j-1]

三、str2删除元素，dp[i][j-1]

四、str2增加元素，dp[i-1][j]

五、其中一个字符串修改元素 dp[i-1][j-1]

综上可知str1删等价于str2增 str2删等价于str1增

因此最后只有三个式子取最小值：min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});