Screenshot from 2016-02-01 22:18:11.png

My code:

public class Solution {
    public int minDistance(String word1, String word2) {
        if (word1 == null || word2 == null)
            return -1;
        else if (word1.length() == 0)
            return word2.length();
        else if (word2.length() == 0)
            return word1.length();
        else if (word1.equals(word2))
            return 0;
        
        int len1 = word1.length();
        int len2 = word2.length();
        /** dp[i][j] means the distance between word1[0, 0 + len1) and word2[0, 0 + len2) */
        int[][] dp = new int[len1 + 1][len2 + 1];
        for (int i = 0; i <= len1; i++)
            dp[i][0] = i;
        for (int i = 0; i <= len2; i++)
            dp[0][i] = i;
        
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                char c1 = word1.charAt(i - 1);
                char c2 = word2.charAt(j - 1);
                if (c1 == c2) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                else {
                    int delete = dp[i - 1][j] + 1;
                    int insert = dp[i][j - 1] + 1;
                    int replace = dp[i - 1][j - 1] + 1;
                    dp[i][j] = Math.min(delete, Math.min(insert, replace));
                }
            }
        }
        
        return dp[len1][len2];
    }
}

這道題木既昨天 scramble string之后，再次刷新我三觀。。。
DP就像是一臺參透天地規(guī)則的機器。放在那里跑。雖然笨，慢，但是，最終結(jié)果，
一定會出來！
一定是正確的！
就是是圖靈機。就像那部電影里破譯電報密碼的機器。
雖然笨重，落后，但是，結(jié)果一定會出來。
說了這么多，實在是感嘆DP的偉大。
雖然也知道做他的思路。但是，真的想不出
dp[i][j] 的具體物理意義。這真的是思維高度不同。
這道題目。
dp[i][j] 表示 word1.substring(0, i) and word2.substring(0, j) 的distance
即word1從開頭，長度為i的子串，和word2從開頭，長度為j的子串，之間的distance。
dp[i][j]
所以，
dp[0][j] = j
dp[i][0] = i
假設現(xiàn)在一個長度分別為 i, j 的子串。那么，
dp[i][j] 等于多少呢？
或者說，他可以由哪幾個變化得到呢？
三個，
delete, insert, replace
假設， c1 = word1.charAt(i); c2 = word2.charAt(j);
if c1 == c2 -> dp[i][j] = dp[i - 1][j - 1];
即，word1[0, i - 1) 變化到 word2[0, j - 1) 的步數(shù)
與 word1[0, i) 變化到 word2[0, j)的步數(shù)相同。 因為末尾字母相同。
這也是變化最小的步數(shù)。

if c1 != c2
那么，就需要多點變化了。三種變化，上面說了。
假設末尾字母分別是 x， y
-------x
-----------y
如果是delete
要從word1變到word2，那么把x刪除，再從word1[0, i - 1) 變到 word2[0, j)
所以，delete變化需要的步數(shù)，
delete = dp[i - 1][j] + 1;

如果是insert
那么，在word1末尾，插入y，或者說，
先將 word1[0, i) 變到word2[0, j - 1), 然后word1末尾再插入y，就行了。
所以，insert變化需要的步數(shù)，
insert = dp[i][j - 1] + 1;

如果是replace，直接把x換成y，
所以，replace變化需要的步數(shù)，
replace = dp[i - 1][j - 1] + 1;

然后找出 這三個步驟操作的步數(shù)中的最小值，作為dp[i][j]
然后一步步往下走。

參考網(wǎng)頁：
http://www.programcreek.com/2013/12/edit-distance-in-java/

真的想不出來。。

Anyway, Good luck, Richardo!

My code:

public class Solution {
    public int minDistance(String word1, String word2) {
        if (word1 == null || word2 == null) {
            return -1;
        }
        
        int row = word1.length() + 1;
        int col = word2.length() + 1;
        
        int[][] dp = new int[row][col];
        for (int i = 1; i < row; i++) {
            dp[i][0] = i;
        }
        for (int i = 1; i < col; i++) {
            dp[0][i] = i;
        }
        
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                int delete = dp[i][j - 1] + 1;
                int add = dp[i - 1][j] + 1;
                int replace = dp[i - 1][j - 1];
                if (word1.charAt(i - 1) != word2.charAt(j - 1)) {
                    replace += 1;
                }
                dp[i][j] = Math.min(delete, Math.min(add, replace));
            }
        }
        
        return dp[row - 1][col - 1];
    }
}

還是靠自己做出來了，感覺和 wildcard matching 很類似
-----i
------j

1. delete: dp[i - 1][j] + 1, delete i
2. add: dp[i][j - 1] + 1, add i + 1 = j
3. replace: dp[i - 1][j - 1] + i == j ? 0 : 1, replace j with i if necessary

Anyway, Good luck, Richardo！ -- 08/17/2016