72. Edit Distance

Photo by Oladimeji Odunsi on Unsplash
Photo by Oladimeji Odunsi on Unsplash
在解此題時,我們要先觀察 word1 如何變成 word2。以 Example1 為例,左下圖列出 “horse” 轉變成 “ros” 的 distance。表中,縱軸表示 “horse”,而橫軸表示 “ros”。

Problem

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

  • Insert a character
  • Delete a character
  • 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')

Constraints:

  • 0 <= word1.length, word2.length <= 500
  • word1 and word2 consist of lowercase English letters.

Solution

在解此題時,我們要先觀察 word1 如何變成 word2。以 Example1 為例,左下圖列出 “horse” 轉變成 “ros” 的 distance。表中,縱軸表示 “horse”,而橫軸表示 “ros”。

第一行,我們先考慮如何空字串轉變成 “ros”。

  • 第一,空字串轉變成空字串,distance 為 0。
  • 第二,空字串轉變成 “r”,distance 為 1,因為要插入一個 “r”。
  • 第三,空字串轉變成 “ro”,distance 為 2,因為要插入一個 “r” 和一個 “o”。
  • 第四,空字串轉變成 “ros”,distance 為 3。

第二行,我們考慮當只有 “horse” 的第一個字母時,也就是 “h” 要如何轉變成 “ros”。第三行,我們考慮 “ho” 要如何轉變成 “ros”。

觀察左下圖後,我們可以發現一些規則。在右下圖的最下面的 “horse” 轉變成 “r” 的距離是 4。我們發現以下的公式:

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

另外,我們還發現另一個規則,也就是右下圖中藍色的部分。當最後的字母相同時,如 “ho” 轉變成 “ro” 和 “hor” 轉變成 “r”,則:

dp[i][j] = dp[i-1][j-1]

結合上述兩個公式,我們可以得出以下公式。

dp[i][j] = \begin{cases} 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) \\\\ dp[i-1][j-1], word_1[i] = word_2[j] \end{cases}

因此,此題便轉變為,利用上面的公式來建立下圖中的表格。最後的答案就會在表格中的最後一個元素,也就是途中綠色的部分。

Dynamic Programming

  • Time: O(mn)
  • Space: O(mn)
class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int j = 1; j <= n; j++) {
            dp[0][j] = j;
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; 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 - 1][j] + 1, Math.min(dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1));
                }
            }
        }

        return dp[m][n];
    }
}

參考

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

You May Also Like
Photo by Diana Parkhouse on Unsplash
Read More

1048. Longest String Chain

此題中,wordA 是 wordB 的 predecessor 指只要插入一個 letter 到 wordA,那就會使得它和 wordB 一樣。然而,插入一個 letter 到一個地方,就要考慮 26 種字母。這使得整體的複雜度上升。
Read More
Photo by Bogdan Farca on Unsplash
Read More

39. Combination Sum

此題要我們列出所有可能的組合,所以我們可能用 backtracking 來找。但是,我們必須避免找到相同的組合。當兩個組合裡的數字和個數都依一樣,但順序不一樣時,他們依然是相同的組合。
Read More