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

#include<bits/stdc++.h>

using namespace std;

int main()
{
    string word1, word2;
    while( cin>>word1>>word2 )
    {
        int n = word1.size(),  m = word2.size();
        if( m*n == 0 ) cout<<(m+n)<<endl;
        int dp[n+1][m+1];
        for( int i=0; i<n+1; i++)  // 删除操作或插入操作
        {
            dp[i][0] = i;
        }
        for( int j=0; j<m+1;j ++)  // B有字符，删除B或插入A
        {
            dp[0][j] = j;
        }

        for( int i=1; i<n+1; ++i )  // 开始循环
        {
            for( int j=1; j<m+1; j++ ) // 开始循环
            {
                int left = dp[i-1][j] +1; // 左边
                int down = dp[i][j-1] +1; // 右边
                int left_down = dp[i-1][j-1];
                if( word1[i-1] != word2[j-1] ) left_down +=1; // i-1就是第i个！修正一下这个字符，如果相等则直接相等
                dp[i][j] = min( left, min( down, left_down) ); // 神奇
            }   
        }
        cout<<dp[n][m]<<endl;
    }
    return 0;
}