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

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

int LevenShteinDistance(string& s1, string& s2) {
    //标准解法是利用动态规划的算法，和0-1背包问题的解法是一回事
    //设定的这个矩阵大小为m+1 * n+1,第i行第j个表示，对于长度为i的s1字符串子串，
    //长度为j的s2字符串子串需要进行多少的个操作数
    vector<vector<int>> dp(s1.size() + 1, vector<int>(s2.size() + 1, 0));
    //第一行和第一列代表，如果另外一个字符串为0的情况下，需要多少个操作数
    //第一行
    for (int i = 1; i != s1.size() + 1; ++i) {
        dp[i][0] = i;
    }
    for (int i = 1; i != s2.size() + 1; ++i) {
        dp[0][i] = i;
    }
    //判断的核心就是如果新添加的字符串,如果和另外一个字符串的最后一位相同，那么就不需要添加额外操作
    //否则需要添加一个操作
    for (int i = 1; i != s1.size() + 1; ++i) {
        for (int j = 1; j != s2.size() + 1; ++j) {
            if (s1[i - 1] == s2[j - 1])
                dp[i][j] = dp[i - 1][j - 1];
            //这个怎么理解呢，假如字符串1取i-1个，字符串2取j-1个，然后把这两个字符串的编辑距离是
            //dp[i-1][j-1]，那么此时，加了一个字符，字符串1是i个，字符串2是j个，那么编辑距离肯定变为
            //假如加的这俩相同，一模一样，是否相当于没有增加任何的操作数，那么dp[i][j] = dp[i-1][j-1]
            else {
                //假如两个不一样呢，字符串1有i个，字符串2的前j-1个，此时的操作数为dp[i][j-1]，字符串2多加一个
                //值，经过这个操作数以后，两个字符串都相同了，突然其中一个加了一个，那么操作数+1；第二种情况就是
                //dp[i-1][j]是字符串1只取前i-1个，然后变成字符串1取前j个的操作数，两者完全一样了，突然给i增加一个字符
                //那么操作数依然得+1；第三种情况就是dp[i-1][j-1]，即经过这个操作数以后，字符串1前i-1个，字符串前j-1个
                //变成了一样的，然后这个时候，各加了一个字符，那么进行一个替换操作，操作数+1
                dp[i][j] = min(dp[i - 1][j - 1] + 1, dp[i][j - 1] + 1);
                dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1);
            }
        }
    }

    return dp[s1.size()][s2.size()];
}


int main() {
    string s1, s2;
    getline(cin, s1);
    getline(cin, s2);
    cout << LevenShteinDistance(s1, s2);
}
// 64 位输出请用 printf("%lld")

解析都写代码里了，自己看吧