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

#include <iostream>
#include <vector>
#include <string>
using namespace std;
/*
双序列问题，将其看成回文串问题的变形，但没有单序列不用长度会无法状态转移的情况
dp[i][j]表示串1的前i位与串2的前j位的编辑距离
当s1[i] == s2[j]时，不用编辑，继承dp[i-1][j-1]的结果就行
当s1[i] != s2[j]时，编辑分为三种情况：
1.s1的i位比s2的j位多一位， dp[i][j] = dp[i-1][j] + 1
2.反之 dp[i][j] = dp[i][j-1] + 1
3.正对着 第i位与第j位不同 两者替换一个就行 dp[i][j] = dp[i-1][j-1] + 1
故取这三方中的最小值即可
*/
int main() {
    string s1,s2;
    while(cin >> s1 >> s2){
        int m = s1.size();
        int n = s2.size();

        vector<vector<int> > dp(m+1,vector<int>(n+1,0));
        for(int i = 1; i <= m; i++) dp[i][0] = i;//串1有字符串二无，编辑距离为串一长度
        for(int j = 1; j <= n; j++) dp[0][j] = j;//与上面相反
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n ; j++){
                if(s1[i-1] != s2[j-1]) //因为dp的下标从1开始，而字符串从0开始
                    dp[i][j] = min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
                else dp[i][j] = dp[i-1][j-1];
            }
        }
        cout << dp[m][n] << endl;
    }
}
// 64 位输出请用 printf("%lld")