[閒聊] LeetCode 72已回收
72. Edit Distance
給你兩個字串word1和word2，我們可以對字串三種操作，分別是：
* 插入一個字元到word1
* 刪除word1的一個字元
* 替換掉word1中的一個字元
我們要找出word1經過上面三種操作後變成word2所需要的最小次數。
Example：
Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')
思路：
1.字串問題大多數都可以採動態規劃處理，首先我們創立一個二維陣列dp[i][j]，
表示長度為 i 的word1 轉換為長度為 j 的word2所需的最小操作次數。
2.找出狀態轉移方程式
我們可以透過下列方式更新矩陣的值：
若s1[i]和s2[j]相同，那麼不需要做任何操作，dp[i][j]會等於dp[i-1][j-1]。
若s1[i]和s2[j]不相同，我們比較插入、刪除、替換這三種操作哪個做最少次：
插入：若我們要插入一個c到s1，需要一次操作且變為s1[1..i] + c，我們可以透過
dp[i][j-1] + 1來更新。
刪除：若我們要從s1刪除一個c，需要一次操作且變為s1[1...i-1]，我們可透過
dp[i-1][j] + 1來更新。
替換：若我們要從s1替換掉一個c，需要一次操作且變為s1[1...i-1] + c ，我們可以透
過dp[i-1][j-1] + 1來更新。
3.決定dp初始條件
因為要檢查dp[i-1][j-1]為了避免越界我們用兩個loop初始化dp[0][j]和dp[i][0]。
4.用雙層loop把dp表格填滿後返回dp[m][n]
JavaCode：
--------------------------------------
class Solution {
public int minDistance(String word1, String word2) {
int m = word1.length();
int n = word2.length();
if (m == 0 || n == 0) {
return m + n;
}
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
dp[i][0] = i;
}
for (int i = 0; i <= n; i++) {
dp[0][i] = i;
}
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][j - 1],
Math.min(dp[i - 1][j], dp[i - 1][j - 1])) + 1;
}
}
}
return dp[m][n];
}
}
--------------------------------------
--
https://i.imgur.com/uiFto42.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.160.97.84 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1669878269.A.F29.html
※ 編輯: Rushia (1.160.97.84 臺灣), 12/01/2022 15:05:01
→
12/01 15:06,
3年前
, 1F
12/01 15:06, 1F
推
12/01 15:06,
3年前
, 2F
12/01 15:06, 2F
推
12/01 15:06,
3年前
, 3F
12/01 15:06, 3F
推
12/01 15:07,
3年前
, 4F
12/01 15:07, 4F
推
12/01 15:08,
3年前
, 5F
12/01 15:08, 5F
推
12/01 15:09,
3年前
, 6F
12/01 15:09, 6F
推
12/01 15:21,
3年前
, 7F
12/01 15:21, 7F