題目：

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:

• Insert a character
• Delete a character
• Replace a character

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

Example2：
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')

思路：

這道題的解體思路主要是動態(tài)規(guī)劃。既然是動態(tài)規(guī)劃那就要明確狀態(tài)數(shù)組的意義以及狀態(tài)方程。

狀態(tài)數(shù)組：dp[i][j]的意義為word1 0-i個字符轉換到word2 0-j個字符的最小的步數(shù)。

狀態(tài)方程：
第i個字符等于第j個字符的時候：

dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j] + 1, dp[i][j-1] + 1))

第i個字符不等于第j個字符的時候：

dp[i][j] = Math.min(dp[i-1][j-1] + 1, Math.min(dp[i-1][j] + 1, dp[i][j-1] + 1))

狀態(tài)方程的解釋：
一旦word1和word2有一個字符相等則需要比較三段字符，這里拿horse和ros來舉例。horse的第四個字符和ros的第三個字符相等。

• 忽略當前的s字符，取hor轉ro的代價。即dp[i-1][j-1]。
• hors轉到ro的代價加一，加上的一是在轉為ro的基礎上插入一個s。即dp[i][j-1] + 1。
• hor轉到ros的代價加一，加上的一是刪除hors中的s，即dp[i-1][j] + 1。

當遍歷到horse的第三個字符和ros的第三個字符時，這兩個字符是不等的。因此需要取ho轉到ro的代價然后加一，加上的一代表著r轉換為s。

注意：dp數(shù)組的長度是word1.length * word2.length。當遍歷到第i個字符的時候在dp數(shù)組中對應的是i+1。這樣做的原因是在遍歷初始行列的時候避免出錯，dp數(shù)組的0行0列首先賦上初始值，之后就可以按照dp公式計算所有字符串轉換的代價了。因為之前做的時候如果遇到orr轉rt的情況賦初始值會很困難，比如orr轉r, o到r為1， or到r為1，orr到r為2, 很難發(fā)現(xiàn)規(guī)律。

horse轉ros的全過程：

horse轉ros的過程

代碼：

public int minDistance(String word1, String word2) {
        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 result = 0;
        int [][] dp = new int [word1.length() + 1][word2.length() + 1];
        for(int i=0;i<=word1.length();i++){
            dp[i][0] = i;
        }
        for(int j=0;j<=word2.length();j++){
            dp[0][j] = j;
        }
        for(int i=1;i<=word1.length();i++){
            for(int j=1;j<=word2.length();j++){
                if(word1.charAt(i-1) == word2.charAt(j-1)){
                    dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j] + 1, dp[i][j-1] + 1));
                }else{
                    dp[i][j] = Math.min(dp[i-1][j-1] + 1, Math.min(dp[i-1][j] + 1, dp[i][j-1] + 1));
                }
            }
        }
        return dp[word1.length()][word2.length()];
}