Leetcode - Edit Distance

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就像是一台参透天地规则的机器。放在那里跑。虽然笨，慢，但是，最终结果，
一定会出来！
一定是正确的！
就是是图灵机。就像那部电影里破译电报密码的机器。
虽然笨重，落后，但是，结果一定会出来。
说了这么多，实在是感叹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
假设现在一个长度分别为 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) 的步数
与 word1[0, i) 变化到 word2[0, j)的步数相同。因为末尾字母相同。
这也是变化最小的步数。

if c1 != c2
那么，就需要多点变化了。三种变化，上面说了。
假设末尾字母分别是 x， y
-------x
-----------y
如果是delete
要从word1变到word2，那么把x删除，再从word1[0, i - 1) 变到 word2[0, j)
所以，delete变化需要的步数，
delete = dp[i - 1][j] + 1;

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

如果是replace，直接把x换成y，
所以，replace变化需要的步数，
replace = dp[i - 1][j - 1] + 1;

然后找出这三个步骤操作的步数中的最小值，作为dp[i][j]
然后一步步往下走。

参考网页：
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

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

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

Leetcode - Edit Distance

推荐阅读更多精彩内容