Edit Distance 119

Question

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

Insert a character

Delete a character

Replace a character

Example

Given word1 = "mart" and word2 = "karma", return 3.

Solution

ed[i][j]表示将word1的前i个字符变成word2的前j个字符所需要的最少操作。

初始化：

ed[i][0]=i 删除i次
ed[0][j]=j 添加j次

状态函数：

如果word1.charAt(i-1)==word2.charAt(j-1)
ed[i][j]=min(min(ed[i-1][j], ed[i][j-1])+1, ed[i-1][j-1])
否则
ed[i][j]=min(min(ed[i-1][j], ed[i][j-1])+1, ed[i-1][j-1]+1)

即word1的前i为字符转换为word2的前j位字符所需的最小操作有三种情况要讨论：

1）将word1的第i位字符删去。此时只要看word1的前i－1位字符转换为word2的前j位字符所需操作再加上刚才的删除操作。

2）将word2的第j位字符删去。此时只要看word1的前i位字符转换为word2的前j－1位字符所需操作再加上刚才的删除操作。

3）将word1的第i位字符转换为word2的第j位字符。此时又分两种情况：1）word1的第i位字符和word2的第j位字符相等，则对于word1的第i位字符和word2的第j位字符无序任何操作，直接看word1的前i－1位字符转换为word2的前j－1位字符所需操作2）word1的第i位字符和word2的第j位字符不相等，则要将word1的第i位字符转换为word2的第j位字符，然后就是1）的情况。

这三种情况里面的最小值就是ed[i][j]的值。

代码如下：

public class Solution {
    /**
     * @param word1 & word2: Two string.
     * @return: The minimum number of steps.
     */
    public int minDistance(String word1, String word2) {
        // write your code here
        if(word1 == null && word2 == null || word1.length() == 0 && word2.length() == 0){
            return 0;
        }

        if(word1 == null || word1.length() == 0){
            return word2.length();
        }

        if(word2 == null || word2.length() == 0){
            return word1.length();
        }

        int n = word1.length();
        int m = word2.length();
        int[][] ed = new int[n + 1][m + 1];

        for(int i = 0; i <=n; i++){
            ed[i][0] = i;
        }

        for(int j = 1; j <= m; j++){
            ed[0][j] = j;
        }

        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                ed[i][j] = Math.min(ed[i - 1][j], ed[i][j - 1]) + 1;
                if(word1.charAt(i - 1) == word2.charAt(j - 1)){
                    ed[i][j] = Math.min(ed[i][j], ed[i - 1][j - 1]);
                }else{
                    ed[i][j] = Math.min(ed[i][j], ed[i - 1][j - 1] + 1);
                }
            }
        }

        return ed[n][m];
    }
}