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

1. a中插入字符，即lev[i][j] = lev[i-1][j] + 1;
2. b中插入字符，即lev[i][j] = lev[i][j-1] + 1;
3. a[i]替换成b[j]，lev[i][j] = lev[i-1][j-1] + 1;

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <sstream>
#include <stack>
#include <map>
using namespace std;
typedef long long ll;

int findMin(int a,int b,int c){
    a = min(a, b);
    b = min(b, c);
    return min(a, b);
}

int solve(string a,string b){
    a.insert(0,1,' ');
    b.insert(0,1,' ');

    int n = a.size(), m = b.size();
    int cost, lev[n][m];

    for(int i = 0; i < n; i++) lev[i][0] = i;
    for(int j = 0; j < m; j++) lev[0][j] = j;

    for(int i=1;i<n;i++){
        for(int j=1;j<m;j++){
            if(a[i]==b[j]) cost=0;
            else cost=1;

            lev[i][j]=findMin(lev[i][j-1]+1,lev[i-1][j]+1,lev[i-1][j-1]+cost);
        }
    }

    return lev[n-1][m-1];
}

int main()
{
    string a,b;
    cin>>a>>b;

    int ans=solve(a,b);
    cout<<ans<<endl;
    return 0;
}