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

#include <bits/stdc++.h>

using namespace std;

//动态规划
int minDistance(string s1, string s2){
//本质不同的操作实际上只有三种：
//在单词 A 中插入一个字符；
//在单词 B 中插入一个字符；
//修改单词 A 的一个字符。
//字符串 A 为空，如从 转换到 ro，显然编辑距离为字符串 B 的长度，这里是 2；
//字符串 B 为空，如从 horse 转换到 ，显然编辑距离为字符串 A 的长度。
//可以使用动态规划来解决这个问题了。
//我们用 D[i][j] 表示 A 的前 i 个字母和 B 的前 j 个字母之间的编辑距离。
    
    int n = s1.size(); int m = s2.size();
    if(n * m == 0) return n + m; //有一个为空
    
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    //边界初始化
    for(int i = 0; i <= n; i++){
        dp[i][0] = i;
    }
    for(int j = 0; j <= m; j++){
        dp[0][j] = j;
    }
    
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(s1[i - 1] == s2[j - 1]){ //
                 //A 的第 i 个字符和 B 的第 j 个字符原本就相同,不需要进行修改操作
                dp[i][j] = min(min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1]);
            }
            else{
                dp[i][j] = min(min(dp[i - 1][j] + 1, dp[i][j - 1] + 1), dp[i - 1][j - 1] + 1);
            }
        }
    }

    return dp[n][m];
  
}

int main(){
    string s1 = "";
    string s2 = "";
    while(cin >> s1 >>s2){
        cout << minDistance(s1, s2) << endl;
    }
    
    return 0;
}