題目描述:給定一個(gè)源串和目標(biāo)串，能夠?qū)υ创M(jìn)行如下操作：在給定位置上插入一個(gè)字符替換任意字符刪除任意字符寫一個(gè)程序，返回最小操作數(shù)，使得對(duì)源串進(jìn)行這些操作后等于目標(biāo)串，源串和目標(biāo)串的長度都小于2000。關(guān)于字符串最短編輯距離的解題思路:給定相關(guān)數(shù)據(jù)的定義:mep[i][j]表示源字符串source[0..i]到目標(biāo)字符串target[0...j]的編輯距離,為了能夠使用動(dòng)態(tài)規(guī)劃來解決相關(guān)的問題,首先要寫出相關(guān)狀態(tài)轉(zhuǎn)移方程.在寫出方程之前,對(duì)上面的題目進(jìn)行分析:假設(shè)給定兩個(gè)字符串source:ALGORITHM,target:ALTRUISTIC,先對(duì)兩個(gè)字符串進(jìn)行對(duì)其操作:A L G O R   I   T H MA L T   R U I S T I Csource[i]與target[j]的對(duì)應(yīng)情況主要分為下面四種情況:字符--字符,字符--空白,空白--字符,空白--空白首先分析第一種情況:字符--字符:    當(dāng)source[i]==target[j]時(shí),mep[i][j]=mep[i-1][j-1];    當(dāng)source[i]!=target[j]時(shí),mep[i][j]=mep[i-1][j-1]+1;字符--空白:    考慮子字符串,也就是說也就說mep[i-1][j]是存在的,因?yàn)槟繕?biāo)串在該位置處為空白,說明j不會(huì)發(fā)生變化,    但是源字符串只有i-1才匹配(狀態(tài)轉(zhuǎn)移);所以mep[i][j]=mep[i-1][j]+1;空白--字符    同理mep[i][j] = mep[i][j-1]+1;空白--空白 忽略綜上所述總的狀態(tài)轉(zhuǎn)移方程為:    mep[i][j]=min(mep[i][j-1]+1,mep[i-1][j]+1,(source[i]==target[j]?0:1))題目二:傳統(tǒng)的編輯距離里面有三種操作，即增、刪、改，我們現(xiàn)在要討論的編輯距離只允許兩種操作，即增加一個(gè)字符、刪除一個(gè)字符。我們求兩個(gè)字符串的這種編輯距離，即把一個(gè)字符串變成另外一個(gè)字符串的最少操作次數(shù)。假定每個(gè)字符串長度不超過1000，只有大寫英文字母組成。根據(jù)題目所述:兩個(gè)字符串進(jìn)行對(duì)其操作A L G O R   I   T H MA L   T R U I S T   I C以上三中情況不會(huì)出現(xiàn):字符--字符情況,把這中情況省略即可
public class MinEditDistance {    static int minEditDistance(String source, String target) {        int SLen = source.length();        int TLen = target.length();        int mep[][] = new int[SLen][TLen];        for (int i = 0; i < SLen; i++) {            mep[i][0] = i;        }        for (int j = 0; j < TLen; j++) {            mep[0][j] = j;        }        for (int i = 1; i < SLen; i++) {            for (int j = 1; j < TLen; j++) {                if (source.charAt(i) == target.charAt(j)) {                    mep[i][j] = mep[i - 1][j - 1];                } else {                    //mep[i][j] = min(mep[i - 1][j] + 1, mep[i][j - 1] + 1);沒有"改"操作時(shí)的算法                    mep[i][j] = min(mep[i-1][j-1]+1,min(mep[i - 1][j] + 1, mep[i][j - 1] + 1));                }            }        }        return mep[SLen - 1][TLen - 1];    }    static int min(int a, int b) {        return a > b ? b : a;    }    public static void main(String[] args) {//        String str = "ALGORITHM";//        String str1 = "ALTRUISTIC";        String str = "math";        String str1 = "mouth";        System.out.PRintln(minEditDistance(str, str1));    }}