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

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

int getMin(int a,int b,int c){
    int x = a<b ?  a:b;
    return x<c ? x:c;
}

int main(){
    string s1,s2;
    std::cin >> s1 >> s2;
    int m=s1.size(),n=s2.size();
    int dp[m+1][n+1];memset(dp,0,sizeof(dp));
    for(int i=0;i<m+1;i++) dp[i][0]=i;
    for(int i=0;i<n+1;i++) dp[0][i]=i;
    for(int i=1;i<m+1;i++){
        for(int j=1;j<n+1;j++){
            if(s1[i-1]==s2[j-1]){
                dp[i][j]=getMin(dp[i-1][j-1],dp[i-1][j]+1,dp[i][j-1]+1);
            }else{
                dp[i][j]=getMin(dp[i-1][j-1]+1, dp[i-1][j]+1, dp[i][j-1]+1);
            }
        }
    }
    std::cout << dp[m][n];
    return 0;
}