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

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main(){
    string s1,s2;
    while(cin>>s1>>s2){
        int m =s1.size();
        int n =s2.size();
        if(m*n==0){
            cout<<m+n;
            return 0;
        }
        int dp[m+1][n+1];
        for(int i=0;i<m+1;i++){
            dp[i][0]=i;
        }
        for(int j=0;j<n+1;j++){
            dp[0][j]=j;
        }
        for(int i=1;i<m+1;i++){
            for(int j=1;j<n+1;j++){
                int left=dp[i-1][j]+1;
                int up=dp[i][j-1]+1;
                int left_up=dp[i-1][j-1];
                if(s1[i-1]!=s2[j-1]){
                    left_up +=1;
                }
                dp[i][j]=min(left,min(up,left_up));
            }
        }
        cout<<dp[m][n]<<endl;
        
        
    }
    return 0;
}

参考了前排题解，采用动态规划的方式。

1.定义一个二维数值dp保存编辑距离，dp[i][j]表示从str2前j个字符的子串到str1前i个字符的子串之间的编辑距离。因此二维数组的两个维度长度应该分别大于需要判断的两个子串；

2.先初始化dp[0][0]=0，表示两个空字符串的编辑距离为0；考虑dp[i][0]表示由空字符串到str1前i个字符组成子串的距离。比如dp[1][0]表示由空字符串变为str1的第一个字符，只需要添加这个字符即可因此dp[1][0]=1,所以dp[i][0]=i;考虑dp[0][j],它表示将str2的前j个字符组成子串变为空字符串的编辑距离。比如dp[0][1]表示将str2的第一个字符删去，因此dp[0][1]=1,所以dp[0][j]=j;

3.再考虑状态转移方程。对于当前dp[i][j],它的左侧dp[i-1][j],上边dp[i][j-1],左上为dp[i-1][j-1] dp[i][j]应当可以从他们三个变化而来，结合dp定义，dp[i][j]可由左边或者上边或者左上变换得到，分别是左边加一，上边加一，左上需要分开讨论，若当前字符str2[j-1]=str1[i-1]则两者直接相等，否则需要变换字符，也是加一；

4.对于3中求得的三个距离，根据定义我们需要最短的那个，因此取最小值即可。