[LeetCode] 72. Edit Distance

轉自LeetCode

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

<Solution>

這題剛開始真的不太懂怎麼下手

後來看了一下資料，要運用到 dynamic programming 的方式 (參考資料)

想法如下

• dp[i][j]，代表的是從 word1[0..i-1] 變換到 word2[0..j-1]的最小步驟，1 <= i < word1.length(), 1<= j < word2.length()

• i = 0，也就是 dp 的 row 0，代表的是從空字串變成 word2，那其實就是將 word2 的每個字元，一個一個 insert 到 word1，所以 dp[0][j] = j

• j = 0，dp 的 col 0，代表從word1 變成空字串，就是把 word1 每個字元一個一個刪掉，所以 dp[i][0] = i

• 接著是一般情況，假設現在要求 dp[i][j]，代表是在看 word1[i-1]和 word2[j-1]，所以已經知道 dp[i-1][j-1]的值了，也就是知道如何將 word1[0..i-2] 轉換成 word2[0..j-2] ，那麼會有以下幾種情況

• word1[i-1] = word2[j-1]，這樣什麼都不用做，所以 dp[i][j] = dp[i-1][j-1]

• 需要 replace : replace(word1[i-1], word2[j-1])，所以 dp[i][j] = dp[i-1][j-1] + 1 (for replace)

• 需要 delete : word1[0..i-2] = word2[0..j-1]，所以 dp[i][j] = dp[i-1][j] + 1 (for delete)

• 需要 insert : word1[0..i-1] + word2[j-1] = word2[0..j-1]，所以 dp[i][j] = dp[i][j-1] + 1 (for insert)

這樣就可以找出推導的公式

if word1[i-1] = word[j-1], dp[i][j] = dp[i-1][j-1]

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

code 如下
c++

kotlin