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
andword2
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。我們發現以下的公式:
另外,我們還發現另一個規則,也就是右下圖中藍色的部分。當最後的字母相同時,如 “ho” 轉變成 “ro” 和 “hor” 轉變成 “r”,則:
結合上述兩個公式,我們可以得出以下公式。
因此,此題便轉變為,利用上面的公式來建立下圖中的表格。最後的答案就會在表格中的最後一個元素,也就是途中綠色的部分。
Dynamic Programming
- Time:
- Space:
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]; } }
參考
- 72. Edit Distance, LeetCode.
- 72. Edit Distance, LeetCode Solutions.