题解 | #计算字符串的编辑距离#
计算字符串的编辑距离
http://www.nowcoder.com/practice/3959837097c7413a961a135d7104c314
#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;
}
