计算字符串的编辑距离

计算字符串的编辑距离

思路：

编辑距离

代码：

#include<iostream>
#include<string>
const int N = 1010;
int f[N][N];

using namespace std;

int main(){
    string s1,s2;
    cin>>s1>>s2;
    int n = s1.size(),m = s2.size();
    s1 = ' ' + s1;
    s2 = ' ' + s2;
    f[0][0] = 0;
    
    for(int i = 1; i <= n; i++) f[i][0] = i;
    for(int j = 1; j <= m; j++) f[0][j] = j;
    
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            f[i][j] = min(f[i - 1][j],f[i][j - 1]) + 1;
            if(s1[i] == s2[j]){
                f[i][j] = min(f[i][j],f[i - 1][j - 1]);
            }
            else f[i][j] = min(f[i][j],f[i - 1][j - 1] + 1);
        }
    }
    cout<<f[n][m];
    return 0;
}