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

#include<iostream>
using namespace std;

int f[1001][1001];    //s1中前i个字符与s2中前j个字符的编辑距离
int Distance(string s1, string s2)
{
    int n = s1.length(),  m = s2.length();
    //初始化f
    for(int i = 0; i < n ;i++)    
        f[i][0] = i;     //要使s1中前i个字符与s2前0个字符相同，只能删除s1前i个
    for(int j = 0; j < m; j++)
        f[0][j] = j;    // 同上，要使s1中前0个字符与s2前j个字符相同，只能s1增加j个
    
    for(int i = 1; i < n ;i++)     //在输入字符串前加了个‘ ’，所以是1~n
        for(int j = 1; j < m; j++)    //同上
        {
            f[i][j] = min(f[i-1][j]+1, f[i][j-1]+1);  //增加or删除
            if(s1[i] != s2[j])
                f[i][j] = min(f[i][j], f[i-1][j-1]+1);  //or替换
            else
                f[i][j] = min(f[i][j], f[i-1][j-1]);
        }
    return f[n-1][m-1];     
}
int main()
{
    string s1,s2;
    cin>>s1; s1 = ' ' + s1;   //小tip，在s前面加一个‘ ’，之后计算编辑距离可以从下标1开始
    cin>>s2; s2 = ' ' + s2;
    cout << Distance(s1, s2);

    return 0;
}