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

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

int main() {
    /*
    dp[i][j] 表示s1[i] 与 s2[j]之间的编辑距离
    i = 0, j = 0时，编辑距离为另一字符串长度
    if s1[i] == s2[j]
        dp[i][j] = dp[i - 1][j - 1]
    else
        dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1 删除一个字符
        dp[i][j] = dp[i - 1][j - 1] + 1 插入一个字符
        dp[i][j] = dp[i - 1][j - 1] + 1 替换一个字符
    */
    string s1, s2;
    cin >> s1 >> s2;
    int row = s1.size();
    int col = s2.size();
    vector<vector<int>> dp(row + 1, vector<int>(col + 1, 0));
    for(int i = 1; i <= col; ++i){
        dp[0][i] = i;
    }
    for(int i = 1; i <= row; ++i){
        dp[i][0] = i;
    }
    for (int i = 1; i <= row; ++i) {
        for (int j = 1; j <= col; ++j) {
            if (s1[i - 1] == s2[j - 1]){
                dp[i][j] = dp[i - 1][j - 1];
            }else{
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;
                dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1);
            }
        }
    }
    cout << dp[row][col] << endl;
}
// 64 位输出请用 printf("%lld")