這篇文章是我在做一道有關(guān)字符串的算法題時(shí)候想把這個(gè)過程記錄下來涎跨，加深一下印象。
先上原題：
編輯距離宣虾，又稱Levenshtein距離（也叫做Edit Distance）惯裕，是指兩個(gè)字串之間，由一個(gè)轉(zhuǎn)成另一個(gè)所需的最少編輯操作次數(shù)绣硝。許可的編輯操作包括將一個(gè)字符替換成另一個(gè)字符蜻势，插入一個(gè)字符，刪除一個(gè)字符鹉胖。
例如將kitten一字轉(zhuǎn)成sitting：
sitten （k->s）
sittin （e->i）
sitting （->g）
所以kitten和sitting的編輯距離是3握玛。俄羅斯科學(xué)家Vladimir Levenshtein在1965年提出這個(gè)概念。
給出兩個(gè)字符串a(chǎn),b次员，求a和b的編輯距離败许。
Input
第1行：字符串a(chǎn)(a的長(zhǎng)度 <= 1000)。
第2行：字符串b(b的長(zhǎng)度 <= 1000)淑蔚。
Output
輸出a和b的編輯距離
Input示例
kitten
sitting
Output示例
3
這道題其實(shí)很經(jīng)典市殷，是利用了上面那個(gè)科學(xué)家發(fā)現(xiàn)的經(jīng)典算法。第一次遇見刹衫，主要是想訓(xùn)練一下字符串相關(guān)的題目醋寝，然后這道題是涉及使用動(dòng)態(tài)規(guī)劃的一道經(jīng)典題目
這道題的思路比較簡(jiǎn)單，但是對(duì)于初學(xué)動(dòng)態(tài)規(guī)劃和算法的我來說带迟，確實(shí)不好想音羞。
思路：
先將兩個(gè)字符串都在開頭加上一個(gè)空格，為了后面動(dòng)態(tài)規(guī)劃處理時(shí)仓犬，在第一個(gè)字符也能有前面的結(jié)果作為基礎(chǔ)嗅绰。比如要是不加空格，那么開頭的第一個(gè)字符就沒法向前尋找結(jié)果搀继。
規(guī)定：
dp[i][j]為處理字符串a(chǎn)前i個(gè)字符編輯成字符串b前j個(gè)字符所需要的距離窘面。也就是操作次數(shù)
如果當(dāng)s1[i]==s2[j] 那么dp[i][j]=dp[i-1][j-1]
因?yàn)槟阆耄趇個(gè)字符和j字符相同叽躯，那么此時(shí)是不需要進(jìn)行任何操作的,也就和dp[i-1][j-1]相等了财边。
如果當(dāng)前i和j位置不同 那么dp[i][j]有三個(gè)狀態(tài)轉(zhuǎn)移方式：
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]
當(dāng)時(shí)的我看到這些東西的時(shí)候也是很懵逼的，第一次對(duì)我這種菜鳥來說確實(shí)不好理解点骑。
下面我上圖來說明一下情況酣难，幫助理解這些狀態(tài)變化的理由
- 第一種情況 s1[i]==s2[j]
因?yàn)榇藭r(shí)這兩個(gè)位置相同 那么dp[i][j]的意思 是字符串a(chǎn)從0-i和字符串b從0到j(luò)所需要的編輯操作次數(shù)谍夭，那么就會(huì)等于dp[i-1][j-1]因?yàn)閕和j相等無需操作。
- 第二種情況 s1[i]!=s2[j]
狀態(tài)轉(zhuǎn)移1： dp[i-1][j]+1
首先我們看左邊部分dp[i-1][j]在圖中代表的就是橙色部分憨募，也就是編輯成橙色部分需要的操作次數(shù)紧索，那么我們現(xiàn)在在這個(gè)圖的基礎(chǔ)上如何變成dp[i][j]呢，我可以在b串的橙色部分基礎(chǔ)上馋嗜，在i位置插入a串的i位置的字符齐板。就變成 了右圖的形式吵瞻。此時(shí)也就形成了dp[i][j]（至于那么刪除a串i位置是怎么解釋葛菇，我一時(shí)間想不明白。還請(qǐng)讀者幫忙解惑評(píng)論一下橡羞，我再把文章更新眯停。非常感謝！）
狀態(tài)轉(zhuǎn)移2： dp[i][j-1]+1
原理同上卿泽，就是調(diào)換一下兩個(gè)串即可莺债。
狀態(tài)轉(zhuǎn)移3： dp[i-1][j-1]+1
首先我們看圖的左半部分，橙色表示dp[i-1][j-1]签夭。那么我們?nèi)绾稳ジ淖內(nèi)p[i][j]呢齐邦，因?yàn)檫@種情況的前提條件是i位置和j位置的字符不相同。那么我們只需要替換字符即可第租，把i位置的字符替換成j位置的或者反過來都是一樣的措拇。變成右邊部分。綠色的字符就是我們調(diào)整后的字符慎宾。然后就形成了dp[i][j]了丐吓。
代碼C++實(shí)現(xiàn)：
#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;
}
/*
狀態(tài)轉(zhuǎn)移：
若a串第i個(gè)與b串第j個(gè)相等，那么dp[i][j]=dp[i-1][j-1]
否則趟据，dp[i][j]可由3個(gè)狀態(tài)轉(zhuǎn)移而來：
①dp[i-1][j-1]+1 把a(bǔ)[i]改為b[j] 等價(jià)于把b[j]改為a[i]
②dp[i-1][j]+1 刪去a[i] 等價(jià)于在b[j]前插入a[i]
③dp[i][j-1]+1 刪去b[j]券犁，等價(jià)于在a[i]前插入b[j]
初始化:dp[0][i]=i dp[i][0]=i
*/
int main()
{
string s1;
string s2;
cin>>s1>>s2;
s1=" "+s1;//前面補(bǔ)充一個(gè)空格
s2=" "+s2;//前面補(bǔ)充一個(gè)空格
int i,j;
int len1,len2;
len1=s1.size();
len2=s2.size();//dp[i][j] 代表 s1前i個(gè)字符和s2前j個(gè)字符的編輯距離
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;
}
