問(wèn)題：給定一個(gè)源串和目標(biāo)串隙袁，能夠?qū)υ创M(jìn)行如下操作：
在給定位置上插入一個(gè)字符
替換任意字符
刪除任意字符
要求寫一個(gè)程序，返回最少的操作數(shù)键畴，使得對(duì)源串進(jìn)行這些操作后等于目標(biāo)串盈罐。源串和目標(biāo)串的長(zhǎng)度都小于2000。
關(guān)于編輯距離
編輯距離（Edit Distance
）损搬，又稱
Levenshtein
距離碧库，是指兩個(gè)字串之間柜与，由一個(gè)轉(zhuǎn)成另一個(gè)所需的最少編輯操作次數(shù)。許可的編輯操作包括將一個(gè)字符替換成另一個(gè)字符嵌灰，插入一個(gè)字符弄匕，刪除一個(gè)字符。
例如將kitten
一字轉(zhuǎn)成
sitting
：
sitten （
k
→
s
）
sittin （
e
→
i
）
sitting （→
g
）
俄羅斯科學(xué)家Vladimir Levenshtein
在
1965
年提出這個(gè)概念沽瞭。
常見的思路是動(dòng)態(tài)規(guī)劃迁匠，下面是簡(jiǎn)單的DP
狀態(tài)方程：
//動(dòng)態(tài)規(guī)劃：
//f[i,j]表示
d[0...i]與
s[0...j]的最小編輯距離，
d為目標(biāo)串驹溃，
s
為源串城丧。
f[i,j] = min { f[i-1,j]+1, f[i,j-1]+1, f[i-1,j-1]+(s[i]==d[j]?0:1) }
//分別表示：添加
1
個(gè)，刪除
1
個(gè)吠架，替換
1
個(gè)（相同就不用替換）芙贫。
Java代碼：
https://github.com/JiangJiafu/Algorithm/blob/master/src/MinimumEditDistance.java
新浪博客放代碼不方便，常常被莫名其妙地更改０；瞧健！轉(zhuǎn)到github上了拐辽。
參考資料：
http://ccl.pku.edu.cn/doubtfire/Course/Computational Linguistics/contents/Minimum Edit Distance.pdf
