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

#include <string>
#include <iostream>
using namespace std;
int main()
{
    string w1,w2;
    while(cin>>w1>>w2)
    {
        int n = w1.length(),m = w2.length();
        int D[n + 1][m + 1];
        for(int i=0;i<=n;i++)D[i][0] = i;//从空串打出
        for(int j=0;j<=m;j++)D[0][j] = j;//从空串打出
        for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
        {
            int l = D[i-1][j]+1;//l代表删去第一个串的j
            int d = D[i][j-1]+1;//d代表删去第二个串的i
            int ld=D[i-1][j-1]+(w1[i-1]!=w2[j-1]?1:0);//ld代表把第一个串的j和第二个串的i替换
            D[i][j] = min(l, min(d, ld));
        }
        cout<<D[n][m]<<endl;
    }
}