[LeetCode]Edit Distance

題目

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:

a) Insert a character
b) Delete a character
c) Replace a character

Example
Given work1=”mart” and work2=”karma”

return 3

解題思路

參考了網上解法，http://www.cnblogs.com/lihaozy/archive/2012/12/31/2840152.html
對於作者給出解答程序沒來得及仔細看，但是二維數組中的下標中有0的元素數據初始化我按照自己的想法來的。

程序

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

        int[][] dp = new int[word1.length()][word2.length()];

        for (int i = 0; i < word1.length(); i++) {
            for (int j = 0; j < word2.length(); j++) {
                if (i == 0 && j == 0) {
                    if (word1.charAt(i) == word2.charAt(j))
                        dp[i][j] = 0;
                    else
                        dp[i][j] = 1;
                } else if (i == 0 || j == 0) {
                    if (word1.charAt(i) == word2.charAt(j))
                        dp[i][j] = Math.max(i, j);
                    else if (i == 0)
                        dp[i][j] = dp[i][j - 1] + 1;
                    else if (j == 0)
                        dp[i][j] = dp[i - 1][j] + 1;
                } else {
                    if (i > 0 && j > 0) {
                        dp[i][j] = dp[i - 1][j - 1]; // 字符相同
                        if (word1.charAt(i) != word2.charAt(j))
                            dp[i][j] = dp[i - 1][j - 1] + 1;// 字符不相同
                    }
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][j] + 1); // 和word1減一個字符比
                    dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + 1); // 和word2減一個字符比
                }
            }
        }
        return dp[word1.length() - 1][word2.length() - 1];
    }
}