給兩個字串，要找最小的編輯次數讓 word1 變成 word2。編輯只有三種操作：insert、delete、replace。
這是hard題，蠻有意思的，可以找出像是基因序列相似的程度，或是字典中找相似的詞。
如果用人的概念去想，要怎麼選，要用哪種換法，基準點在哪裡，似乎不是那麼好想像的。
但是能確定朝著每個操作，是 word1 和 word2 之間的交換。
舉例：word1 = ABC, word2 = BABC。
可以想到把 word2[0]做delete，或 word1 insert(0,"B")，就可以得到 word1 == word2。
為了好講，這裡不探討 word2 上做操作，統一以 word1 當基準，也就是只看 word1 -> word2。
像是 word1[0] == word2[1] == "A"，在這位置上不用操作，因為二者相等。說到「位置」這裡換個思考 DP[p1][p2] ，
二者的方向關係是一個表格DP，若 word1[p1] == word2[p2] ， 則 dp[p1][2] 的基本值等於0，即不需要任何操作，反之則 1。
題目要找出最小操作次數，也可以想像把操作數往右下角，一路取最小壘加，最後的結果就是最小操作次數。
如果 word1[p1] != word2[p2]，代表要進行操作，在 DP[p1][p2] 取 {DP[p1-1][p2-1], DP[p1-1][p2], DP[p1][p2-1]}三者最小值加 1 (基本值)。
分別對應{replace, delete, insert}三種操作中取最佳方案到DP[p1][p2] ，看 DP[p1][p2] 的「相對位置」來決定是哪種操作，本身基本值 1 有三種操作的可能，至少一定是其中一個。
ＢＡＢＣ
Ａ１１
Ｂ１Ｘ
Ｃ
在位置[0][1]，[0][0] 是 [p1][p2-1]，即[0][0] insert(0, Char) (B)
在位置[1][0]，[0][0] 是 [p1-1][p2]，即[0][0] del word1[0] (A)
在Ｘ位置[1][1]，對X位置來[0][0]位罝是 replace (A -> B) ，[0][1]位置是 del word1[0]，而 [1][0] insert(1, Char)。
那 word1[p1] == word2[p2] 時呢？ DP[p1][p2] = ？
我們取右下角代表經過操作次數使從頭到p1,p2位置都對上，最右下角即從頭到尾都對上的操作次數。
一旦 word1[p1] == word2[p2]，所需要的次數，即前面都對上所需要的次數，DP[p1][p2] = DP[p1-1][p2-1]。(左上那個 相當於子問題(二字串編輯)的解)
如果在 row = 0 或 col = 0 時 word1[p1] == word2[p2] 相等， DP[p1-1][p2-1] 會超出範圍。那該等於多少？
要是相等，那麼要加上使前面相等的次數。如果是[0][0]，那麼就是0 次， 如果是 [1][0] 或 [0][1]，那麼前面要一樣，不是 delete 就是 insert 前面的，為 1 次。
同理[p1][0]、[0][p2]，邊際無法做 replace，建議獨立出來處理掉。
像這種有邊際問題的，可以增加表格範圍(邊際欄列)，又或者先拿出來處理。如果把邊際的條件寫在一起，不僅不方便讀，也拖累效率。
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
from functools import lru_cache
rows, cols = len(word1)+1, len(word2)+1
@lru_cache(None)
def dfs(row, col):
if row == 0 or col == 0:
return max(row, col)
other = set()
if row > 0 or col > 0:
if word1[row-1] == word2[col-1]:
ans = dfs(row-1, col-1)
else:
if row > 0 and col > 0:
other.add(dfs(row-1, col-1))
if row > 0:
other.add(dfs(row-1, col))
if col > 0:
other.add(dfs(row, col-1))
ans = min(other)+1
return int(ans)
return dfs(rows-1, cols-1)
C#
public class Solution {
public int MinDistance(string word1, string word2) {
var memo = new int[word1.Length+1, word2.Length+1];
for(int i = 0; i < word1.Length+1; i++)
memo[i, 0] = i;
for(int j = 0; j < word2.Length+1; j++)
memo[0, j] = j;
for(int i = 1; i < word1.Length + 1; i++)
{
for(int j = 1; j < word2.Length + 1; j++)
{
if(word1[i-1] == word2[j-1])
memo[i, j] = memo[i-1, j-1];
else
{
memo[i, j] = Math.Min(memo[i-1, j], memo[i, j-1]);
memo[i, j] = Math.Min(memo[i, j], memo[i-1, j-1]) + 1;
}
}
}
return memo[word1.Length, word2.Length];
}
}