這題也是Leetcode上面，Hard難度的題目．雖然表面上看起來很困難，實際解法也不容易想到，但是最後的解答卻精緻輕巧，很有趣

題目是這樣的：

給定兩個字串s1與s2

可以對字串中的字元做以下的操作:

1.插入一個字元

2.刪除一個字元

3.替換一個字元

請問要將s1轉換成s2，最少需要幾個步驟？

例如：s1 = “intention” s2=”execution” 那麼應該返回5，代表需要5步來達成

1.刪除第一個t ⇒ inention

2.將第一個i替換成e ⇒ enention

3.將第一個n替換成x ⇒ exention

4.將第一個n 替換成c ⇒exection

5.插入一個字元u在c與t中間 ⇒execution

這題不用動態規劃，會十分難解

思考過程

之前說過，兩個字串的dp 矩陣比較常用一個二維矩陣來表示，而dp[i,j]，也就是矩陣的最後一個元素通常都是要求得答案．

然後，填入dp的過程中 ，我們會發現其實可以進行的操作不是三種，而是四種．多出來的就是 “什麼都不做”，這是當兩邊的字元相同，那麼我們可以不用進行插入刪除替換中的任何一種，而是直接往下一步前進．

另外一個狀況，就是當s2已經走完了，而s1還沒走完，那這樣也很簡單，我們不停執行刪除字元操作，將s1多餘的部分刪除，直到跟s2長度相同．

反方面來說s1如果先走完了，但是還沒轉換成s2，那麼我們就不停插入s2的字元，直到s1跟s2的長度相同．

所以sudo Code寫成這樣

if(s1[i]==s2[j]){
	//不用做事
	//i,j向前移動
}else{
	三選一:
	插入
	刪除
	替換
}

可以看出這已經可以直接帶入動態規劃的框架了

狀態:演算法在推進過程中變化的變數，這邊就是指標 i j 的位置

選擇:針對每一個狀態可以做得下一步選擇，也就是 跳過skip 插入insert 刪除delete 替換 replace

有了框架，那我們就可以實作了

fun minDistance(s1: String, s2: String): Int {
    fun dp(i: Int, j: Int): Int {
        if (i == -1) return j + 1
        if (j == -1) return i + 1

        return if (s1[i] == s2[j]) {
            dp(i - 1, j - 1) //相同 所以不用做任何操作
        } else {
            val insert = dp(i, j - 1) + 1 //插入操作
            val delete = dp(i - 1, j) + 1 //刪除操作
            val replace = dp(i - 1, j - 1) + 1 //替換操作
						//找出三個操作中最少的那個
            return insert.coerceAtMost(delete).coerceAtMost(replace)
        }
    }
    return dp(s1.length - 1, s2.length - 1)
}

為什麼這些操作要用這樣表達呢

1.s1[i] == s2[j] //相等不用操作

本來就相等了，所以不用做任何操作

s1[0..i]與s2[0..j]的最小編輯距離等於s1[0..i-1]與s2[0..j-1]的最小編輯距離

⇒dp(i,j) = dp(i-1,j-1)

而到了s1[i] ≠s2[j]的情況

2. insert = dp(i, j - 1) + 1 //插入操作

直接在s1[i]中插入一個跟s2[j]一樣的字元

那麼s2[j]就有相符的字元，那向頭移動一位繼續跟s1[i]比較

ex: s1 = “abce” , s2=”badce”

⇒dp(3,4) ： s1[3],s2[4]都是e 所以不用特別處理 dp(3,4) = dp(3-1,4-1) = dp(2,3)

⇒dp(2,3) ： s1[2],s2[3]都是c 所以不用特別處理 dp(2,3) = dp(2-1,3-1) = dp(1,2)

⇒dp(1,2) ： s1[1]= b ,s2[2] = d， 我們s1 的b 後面補上一位 d ，讓s1變長，同時末幾位還是跟s2的末幾位相同

s1 = “abdce” (變長了，而且尾巴跟s2一樣都是dce了)

⇒要比的下一位 應該就是s2的dce之前的那一位元 也就是a，而比較的對象是s1的dce之前的那個位元，看了一下，還是剛剛的s1[1] = b

⇒所以在插入後．是使j-1來比較，別忘了插入的動作也算是一步所以要+1

⇒ val insert = dp(i, j - 1) + 1

3.delete = dp(i - 1, j) + 1 //刪除操作

直接刪除這個字元

⇒通常發生在s2比較短，在s1走完前s2就已經走完了

⇒一路刪除直到兩個長度相等

ex: s1 = “abce” , s2=”c”

⇒dp(3,0) ： s1[3]= e ,s2[0] = c，在s1後面插入一位元c s1 = “abcec”

⇒i繼續前移，跟j的值做比較，別忘了刪除的動作也算是一步所以要+1

⇒val delete = dp(i - 1, j) + 1

4. replace = dp(i - 1, j - 1) + 1 //替換操作

將s1[i] 換成s2[j]這樣兩邊就相等了

同時i,j往前移動繼續以較

ex: s1 = “abce” , s2=”badxz”

⇒dp(3,4) ： s1[3] = e, s2[4] = z 所以把s1[3]換成z s1 = “abcz”

⇒既然已經相等了 ，那就該比較下一位了，別忘了替換的動作也算是一步所以要+1

⇒val replace = dp(i - 1, j - 1) + 1

透過這個演算法，這樣我們就能夠得到答案，但是這個解法是暴力演算法，效率不高

我們明天會來優化這個做法