线性DP求最短编辑距离
算法思想;
使用闫氏DP分析法进行分析,首先是状态表示,使用数组f[i][j]
来表示将a的前i个字符匹配成b的前j个字符要经过多少步操作,再进行状态表示的过程中对其进行分类:
1. 如果是删除a中的一个字符使得a字符串成功匹配到b字符串之后,此时可以转化为a的前i-1
个字符和b的前j
个字符进行匹配的操作数加1即f[i-1][j]+1
;
2. 如果是增加a中的一个字符使得a字符成功匹配到b字符串,此时可以转化成a的前i个字符和b的前j-1
个字符进行匹配的操作数+1,即f[i][j-1]+1
;
3. 如果是修改a中的一个字符使得a字符串成功匹配到b字符串,此时如果a[i]!=b[j]
,可以转化成a的前i-1
个字符和b的前i-1
个字符进行成功匹配的操作数+1,如果a[i]==b[j]
,则两者不需要加1;
注意事项:
- 在输入数据之后要对字符串的各种匹配数字进行初始化操作,要将长度为n的字符串a匹配成长度为0的b字符串,要进行n步操作;要将长度为0的a字符串匹配成长度为m的b字符串,要进行m次添加操作;
- 在两重for循环中,对于
a[i]==b[j]
这种情况进行特殊的判断; - 输入两个字符串a和b的时候要注意从下标为1开始输入;
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int n,m;
char a[N],b[N];
int f[N][N];
int main()
{
cin>>n>>a+1;
cin>>m>>b+1;
//对f数组进行初始化操作
//如果a数组为0,要使得两者匹配,要对b数组进行m次删除操作
for(int i=0;i<=m;i++) f[0][i]=i;
//如果b数组为0,要使得两者匹配,要对a数组进行n次删除操作
for(int i=0;i<=n;i++) f[i][0]=i;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1);
if(a[i]==b[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;
}