大廠面試真題詳解：編輯距離

給出兩個單詞word1和word2，計算出将word1 轉換為word2的最少操作次數。

你總共三種操作方法：

• 插入一個字元
• 删除一個字元
• 替換一個字元

線上評測位址：

領扣題庫官網

樣例 1:

輸入: 
"horse"
"ros"
輸出: 3           

解釋:

horse -> rorse (替換 'h' 為 'r')

rorse -> rose (删除 'r')

rose -> ros (删除 'e')

樣例 2:

輸入: 
"intention"
"execution"
輸出: 5           

intention -> inention (删除 't')

inention -> enention (替換 'i' 為 'e')

enention -> exention (替換 'n' 為 'x')

exention -> exection (替換 'n' 為 'c')

exection -> execution (插入 'u')

算法：DP

經典的二維dp。

更多DP解題技巧，點選此處免費試聽

定義fi為word1前i個字元到word2的前j個字元的轉化的最小步。

接着，我們來考慮狀态轉移方程。

• 假設對于fi以前的之都已知，考慮fi的情形。
• 若word1[i] = word2[j]，那麼說明隻要word1的前i-1個能轉換到word2的前j-1個即可，是以 fi = fi-1
• 反之，若不等，我們就要考慮以下情形了。
• 給word1插入一個和word2最後的字母相同的字母，這時word1和word2的最後一個字母就一樣了，此時編輯距離等于1（插入操作） + 插入前的word1到word2去掉最後一個字母後的編輯距離 fi + 1
• 删除word1的最後一個字母，此時編輯距離等于1（删除操作） + word1去掉最後一個字母到word2的編輯距離 fi - 1 + 1
• 把word1的最後一個字母替換成word2的最後一個字母，此時編輯距離等于 1（替換操作） + word1和word2去掉最後一個字母的編輯距離。為fi - 1 + 1
• 三者取最小值即可。

複雜度分析

• 時間複雜度O(n^2)
  • 二維dp
• 空間複雜度O(n^2)
  • 需要儲存二維的狀态數

public class Solution {
    public int minDistance(String word1, String word2) {
        int n = word1.length();
        int m = word2.length();

        int[][] dp = new int[n+1][m+1];
        for (int i = 0; i < m + 1; i++) {
            dp[0][i] = i; 
        }

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

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

更多題解參考：

九章官網solution