72. Edit Distance

72. Edit Distance

Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

You have the following 3 operations permitted on a word:

1. Insert a character

2. Delete a character

3. Replace a character

Example 1:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation: 
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: 
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')

My Solutions：

先初始化matrix， "_"代表空集。 "_" -> "cca" = 3 操作是插入'c','c','a'，共3步。 "abab" -> "_" 删除'a','b','a','b'，共4 步。

	_	a	b	a	b	d
_	0	1	2	3	4	5
c	1
c	2
a	3
b	4
a	5
b	6

D[i][j] 的递推公式： 从上一个状态到D[i][j]，最后一步只有三种可能：添加，删除，替换（如果相等就不需要替换）

a、添加：给word1插入一个和word2最后的字母相同的字母。编辑距离等于1（插入操作） + 插入前的word1到word2去掉最后一个字母后的编辑距离，即D[i][j - 1] + 1 b、删除：删去word1的最后一个字母。编辑距离等于1（删除操作） + word1去掉最后一个字母到word2的编辑距离，即D[i - 1][j] + 1 c 、替换：把word1的最后一个字母替换成word2的最后一个字母。编辑距离等于 1（替换操作） + word1和word2去掉最后一个字母的编辑距离。 这里有2种情况，如果最后一个字符是相同的，即是：D[i - 1][j - 1]，因为根本不需要替换，否则需要替换，就是D[i - 1][j - 1] + 1

总结:

最后一个字母不相同:D[i][j] = Math.min(D[i][j - 1], Math.min(D[i - 1][j], D[i - 1][j - 1])) + 1;

不然: D[i][j] = D[i - 1][j - 1];

Time & Space Complexity: O(len1 * len2)

class Solution {
    public int minDistance(String word1, String word2) {
        if (word1 == null && word2 == null) return 0;
        if (word1 == null || word1.length() == 0) return word2.length();
        if (word2 == null || word2.length() == 0) return word1.length();
        
        int len1 = word1.length();
        int len2 = word2.length();
        
        int[][] dp = new int[len1 + 1][len2 + 1];
        
        for (int i = 0; i <= len1; i++) dp[i][0] = i;
        for (int j = 1; j <= len2; j++) dp[0][j] = j;
        
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1];
                else dp[i][j] = Math.min(dp[i][j - 1], Math.min(dp[i - 1][j], dp[i - 1][j - 1])) + 1;
            }
        }
        
        return dp[len1][len2];
    }
}