編輯距離是一種衡量兩個相似字符串相似性的度量方法弟头。距離越大相似度越小吩抓。具體地，兩個字符串的編輯距離是其中一個字符串要變換為另一個字符串所需要的最小編輯次數(shù)赴恨。其中編輯操作包含3種：增加一個字符疹娶，刪除一個字符，更改一個字符伦连。
使用編輯距離可以用來進行用戶輸入糾錯雨饺。比如sql語句有select insert update insert等合法命令，若用戶輸入selet惑淳，則可以計算selet與合法命令的編輯距離额港，找到距離最近的命令(select)提示用戶進行更正。當然歧焦，編輯距離不止于此移斩。
計算編輯距離的源碼如下
public static int editDist(String a, String b, int i, int j) {
if (i == -1 || j == -1) {
return Math.max(i+1, j+1);
}
ArrayList<Integer> list = new ArrayList<>();
list.add(editDist(a, b, i - 1, j) + 1);
list.add(editDist(a, b, i, j - 1) + 1);
list.add(editDist(a, b, i - 1, j - 1) + (a.charAt(i) == b.charAt(j) ? 0 : 1));
return Collections.min(list);
}
計算編輯距離的程序雖然簡短，但并不簡單绢馍。其并不是企圖將其中一個字符串通過編輯變?yōu)榱硗庖粋€向瓷，而是利用了編輯距離的如下性質(zhì):
假設(shè)字符串s1，s2經(jīng)過編輯操作變換后變?yōu)閠1舰涌，t2猖任。則若s1，s2都應(yīng)用了相同的編輯操作瓷耙，則s1與s2的編輯距離應(yīng)該等于t1與t2的編輯距離朱躺，否則s1，s2的編輯距離為t1與t2編輯距離加上不同的編輯操作次數(shù)哺徊。
利用如上性質(zhì)室琢，我們可以設(shè)計一些操作將兩個字符串s1，s2經(jīng)過最小次編輯后都變?yōu)榭沾渥贰Ｓ捎趖1盈滴，t2變?yōu)榭眨庉嬀嚯x為0，則最小的不同編輯次數(shù)就是所求的編輯距離巢钓。
于是算法設(shè)計了三種編輯操作病苗，目的是將兩個字符串分別約簡為空串。涉及的操作有兩種
- 刪除第一個字符串的末尾字符
- 刪除第二個字符串的末尾字符
- 同時刪除兩個字符串的末尾字符
很顯然操作1,2會增加原始字符串的編輯距離症汹，而操作3若刪除的字符相同則不增加編輯距離硫朦，否則也增加編輯距離。
經(jīng)過如上定義背镇，求編輯距離的問題就轉(zhuǎn)化為如何用最小的編輯距離距離增量將兩個字符串都約簡為空串咬展。
算法用動態(tài)規(guī)劃來解決這個轉(zhuǎn)化后的問題，故而得到如上算法瞒斩。
通過編輯距離分析編輯距離的求解方法破婆，我們可以得到啟示，有時候可以利用定義本身的性質(zhì)來將原問題轉(zhuǎn)化為更易解決的問題胸囱，再去變成實現(xiàn)祷舀。
