算法非原創(chuàng)燥撞，只是整理厂庇，并嘗試說(shuō)的更完整和易理解渠啊。
字符串編輯距離是什么
將一個(gè)字符串轉(zhuǎn)換成另一個(gè)字符串時(shí)需要付出的代價(jià)。轉(zhuǎn)換可以采用插入权旷、刪除昭抒、替換三種編輯方式。比如說(shuō)把字符串“post”轉(zhuǎn)換成“get”炼杖，直觀看來(lái)它們的編輯距離頗大灭返，并有許多種轉(zhuǎn)換方式。第一種[替換p為g坤邪，替換o為e熙含，刪除
s]這樣它們的轉(zhuǎn)換代價(jià)為3。第二種[刪除p艇纺，刪除o怎静，刪除s邮弹，刪除g，刪除e]這樣它們的轉(zhuǎn)換代價(jià)為5蚓聘。不同的轉(zhuǎn)換方式需要的編輯次數(shù)不一樣腌乡，最少的那個(gè)編輯方式所需的次數(shù)就是這量字符串的編輯距離。
簡(jiǎn)單的遞歸算法
咋一看這個(gè)問(wèn)題似乎挺難夜牡，因?yàn)閷?duì)同一個(gè)字符串需要選擇在不同位置上采用不同的動(dòng)作才能完成任務(wù)与纽，可能會(huì)有一種無(wú)法下手的感覺(jué)。但是用計(jì)算機(jī)的思維方式來(lái)看塘装，我們可以把一個(gè)復(fù)雜的大問(wèn)題轉(zhuǎn)換成一系列簡(jiǎn)單的小問(wèn)題急迂，有多
簡(jiǎn)單呢？比如要把“post”轉(zhuǎn)換成“get”,我們可以先考慮如何用最小的代價(jià)把“post”轉(zhuǎn)換成“et”,或者是把“ost”轉(zhuǎn)換成“get”z或者是把“ost”轉(zhuǎn)換成“et”蹦肴，總之是嘗試用三種辦法（插入僚碎、刪除、替換）使問(wèn)題的復(fù)雜度降級(jí)阴幌，也就是用> 一種遞歸的方式去處理.因?yàn)閷?duì)每一步轉(zhuǎn)換可選擇三種不同的方式(插入勺阐、刪除、替換)矛双，所以需要對(duì)比每一部的最優(yōu)方式渊抽。為了調(diào)試簡(jiǎn)單所以就用js做示例。
function editDis(str1,str2){
if(str1.length==0||str2.length==0){
return Math.abs(str1.length-str2.length)
}
if(str1.charAt(0)===str2.charAt(0)){
return editDis(str1.substr(1,str1.length),str2.substr(1,str2.length))
}
var edInsert = editDis(str1,str2.substr(1,str2.length))+1;
var edDelete = editDis(str1.substr(1,str1.substr.length),str2)+1;
var edReplace = editDis(str1.substr(1,str1.substr.length),str2.substr(1,str2.length))+1;
return Math.min(edInsert,edDelete,edReplace);
}
運(yùn)行結(jié)果如下
editDis("post","get")
3
優(yōu)化的遞歸算法
可以看到上邊的簡(jiǎn)單算法就可以得出正確的結(jié)果了背零，雖然簡(jiǎn)單卻造成了大量的計(jì)算浪費(fèi)腰吟，時(shí)間復(fù)雜度太高，在很多子串上做了重復(fù)計(jì)算徙瓶。優(yōu)化毛雇？最先想到的是什么？做緩存啊侦镇，把計(jì)算過(guò)的結(jié)果存在表里下次計(jì)算首先查表就可以了灵疮。
照我的習(xí)慣就直接弄一個(gè)map做緩存了，但本文的主題不還有動(dòng)態(tài)規(guī)劃么壳繁，所以考慮用動(dòng)態(tài)規(guī)劃的思想去解決震捣。動(dòng)態(tài)規(guī)劃算法通常基于一個(gè)遞推公式及一個(gè)或多個(gè)初始狀態(tài)闹炉，當(dāng)前問(wèn)題的解由上一子問(wèn)題的解推出蒿赢。對(duì)我們的問(wèn)題來(lái)說(shuō)> ，遞歸仍然是最容易的辦法渣触，只不過(guò)可以把每一步子問(wèn)題的解也就是狀態(tài)存表供可能存在的其它子問(wèn)題使用羡棵，其實(shí)對(duì)這個(gè)問(wèn)題來(lái)說(shuō)還是緩存啦。嗅钻。
var editStatusArr = Array(Array())
function editDisWithStatus(str1,str2,x,y){
if(x==0&&y==0){
for(i=0;i<=str1.length;i++)
editStatusArr[i]=Array();
}
if(editStatusArr[x]!=undefined&&editStatusArr[x][y]!=undefined){
console.log(x+"_"+y);
return editStatusArr[x][y];
} else {
var dis = 0;
if((str1.length)==0){
dis = str2.length;
} else if((str2.length)==0){
dis = str1.length;
} else {
if(str1.charAt(0)===str2.charAt(0)){
dis = editDisWithStatus(str1.substr(1,str1.length),str2.substr(1,str2.length),x+1,y+1);
} else {
var edInsert = editDisWithStatus(str1,str2.substr(1,str2.length),x,y+1)+1;
var edDelete = editDisWithStatus(str1.substr(1,str1.substr.length),str2,x+1,y)+1;
var edReplace = editDisWithStatus(str1.substr(1,str1.substr.length),str2.substr(1,str2.length),x+1,y+1)+1;
dis = Math.min(edInsert,edDelete,edReplace);
}
}
editStatusArr[x][y]= dis;
console.log("x:"+x+" y:"+y+" dis:"+dis);
return dis;
}
}
運(yùn)行結(jié)果如下
editDisWithStatus("post","get",0,0)
3
遞推算法
有了上面遞歸的實(shí)現(xiàn)皂冰，我們基本上可以確定遞推關(guān)系了．吶店展，就是下面這個(gè)樣子，首先把其中一個(gè)字串的字符拆開(kāi)排好秃流，然后在下面標(biāo)上１２３４赂蕴，１前面畫(huà)０，然后在縱向上在１下面畫(huà)１２３舶胀，左側(cè)表上另一個(gè)字串的字符．這樣
遞推關(guān)系的初始態(tài)就有了概说，接下來(lái)就是填其它的數(shù)字了，要確定一個(gè)空位的數(shù)字首先看該空位對(duì)應(yīng)的兩個(gè)字符是否一樣峻贮，如果一樣的話就取該空位左席怪，左上应闯，上纤控，三個(gè)方向上的最小值，如果不一樣就取三個(gè)方向上的最小值加１．嗯
碉纺？你不要騙我船万！這和遞歸的實(shí)現(xiàn)根本不相似．遞歸是從最復(fù)雜的一步開(kāi)始思考，由繁至簡(jiǎn)．而遞推是從初始態(tài)開(kāi)始的骨田，由簡(jiǎn)至繁．其實(shí)是差不多的．
| p | o | s | t | ||
|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | |
| g | 1 | 1 | 2 | 3 | 4 |
| e | 2 | 2 | 2 | 3 | 4 |
| t | 3 | 3 | 3 | 3 | 3 |
function editDis(str1,str2){
var editStatusArr = Array(Array())
var i=0,j=0;
for(i=0;i<=str1.length;i++){
editStatusArr[i]=Array();
}
for(j=0;j<=str2.length;j++){
editStatusArr[0][j]=j;
}
for(i=0;i<=str1.length;i++){
editStatusArr[i][0]=i;
}
for(i=1;i<=str1.length;i++){
for(j=1;j<=str2.length;j++){
if(str1.charAt(i-1)===str2.charAt(j-1)){
editStatusArr[i][j]=editStatusArr[i-1][j-1];
} else {
editStatusArr[i][j]=Math.min(editStatusArr[i][j-1],editStatusArr[i-1][j],editStatusArr[i-1][j-1])+1;
}
}
}
return editStatusArr[i-1][j-1];
}
