这篇文章是我在做一道有关字符串的算法题时候想把这个过程记录下来，加深一下印象。
先上原题：
编辑距离，又称Levenshtein距离（也叫做Edit Distance），是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。
例如将kitten一字转成sitting：
sitten （k->s）
sittin （e->i）
sitting （->g）
所以kitten和sitting的编辑距离是3。俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念。
给出两个字符串a,b，求a和b的编辑距离。
Input
第1行：字符串a(a的长度 <= 1000)。
第2行：字符串b(b的长度 <= 1000)。
Output
输出a和b的编辑距离
Input示例
kitten
sitting
Output示例
3
这道题其实很经典，是利用了上面那个科学家发现的经典算法。第一次遇见，主要是想训练一下字符串相关的题目，然后这道题是涉及使用动态规划的一道经典题目
这道题的思路比较简单，但是对于初学动态规划和算法的我来说，确实不好想。
思路：
先将两个字符串都在开头加上一个空格，为了后面动态规划处理时，在第一个字符也能有前面的结果作为基础。比如要是不加空格，那么开头的第一个字符就没法向前寻找结果。
规定：
dp[i][j]为处理字符串a前i个字符编辑成字符串b前j个字符所需要的距离。也就是操作次数
如果当s1[i]==s2[j] 那么dp[i][j]=dp[i-1][j-1]
因为你想，第i个字符和j字符相同，那么此时是不需要进行任何操作的,也就和dp[i-1][j-1]相等了。
如果当前i和j位置不同 那么dp[i][j]有三个状态转移方式：
dp[i-1][j]+1 在a串的i位置删除a[i] (或者在b串的i位置加上a[i])
dp[i][j-1]+1 在b串的j位置删除b[j] (或者在a串的j位置加上b[j])
dp[i-1][j-1]+1 在a串的i位置改a[i]变成b[j]或者在b串的j位置改b[j]为a[i]
当时的我看到这些东西的时候也是很懵逼的，第一次对我这种菜鸟来说确实不好理解。
下面我上图来说明一下情况，帮助理解这些状态变化的理由
- 第一种情况 s1[i]==s2[j]
i和j位置上的字符相同
因为此时这两个位置相同 那么dp[i][j]的意思 是字符串a从0-i和字符串b从0到j所需要的编辑操作次数，那么就会等于dp[i-1][j-1]因为i和j相等无需操作。
- 第二种情况 s1[i]!=s2[j]
i和j位置上的字符不相同
状态转移1： dp[i-1][j]+1
看图理解
首先我们看左边部分dp[i-1][j]在图中代表的就是橙色部分，也就是编辑成橙色部分需要的操作次数，那么我们现在在这个图的基础上如何变成dp[i][j]呢，我可以在b串的橙色部分基础上，在i位置插入a串的i位置的字符。就变成 了右图的形式。此时也就形成了dp[i][j]（至于那么删除a串i位置是怎么解释，我一时间想不明白。还请读者帮忙解惑评论一下，我再把文章更新。非常感谢！）
状态转移2： dp[i][j-1]+1
原理同上，就是调换一下两个串即可。
状态转移3： dp[i-1][j-1]+1
看图理解
首先我们看图的左半部分，橙色表示dp[i-1][j-1]。那么我们如何去改变去dp[i][j]呢，因为这种情况的前提条件是i位置和j位置的字符不相同。那么我们只需要替换字符即可，把i位置的字符替换成j位置的或者反过来都是一样的。变成右边部分。绿色的字符就是我们调整后的字符。然后就形成了dp[i][j]了。
代码C++实现：
#include <iostream>
#include <string>
using namespace std;
const int N=1000;
int dp[N+1][N+1];
int min(int a,int b)
{
return a>b?b:a;
}
/*
状态转移：
若a串第i个与b串第j个相等，那么dp[i][j]=dp[i-1][j-1]
否则，dp[i][j]可由3个状态转移而来：
①dp[i-1][j-1]+1 把a[i]改为b[j] 等价于把b[j]改为a[i]
②dp[i-1][j]+1 删去a[i] 等价于在b[j]前插入a[i]
③dp[i][j-1]+1 删去b[j]，等价于在a[i]前插入b[j]
初始化:dp[0][i]=i dp[i][0]=i
*/
int main()
{
string s1;
string s2;
cin>>s1>>s2;
s1=" "+s1;//前面补充一个空格
s2=" "+s2;//前面补充一个空格
int i,j;
int len1,len2;
len1=s1.size();
len2=s2.size();//dp[i][j] 代表 s1前i个字符和s2前j个字符的编辑距离
for(i=1;i<len1;i++)
{
dp[0][i]=i;
}
for(i=1;i<len2;i++)
{
dp[i][0]=i;
}
for(i=1;i<=len1;i++)
{
for(j=1;j<=len2;j++)
{
if(s1[i]==s2[j])
{
dp[i][j]=dp[i-1][j-1];
}
else
{
dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
}
}
}
cout<<dp[len1][len2]<<endl;
return 0;
}
网友评论