編輯距離

編輯距離定義：

編輯距離,也叫萊文斯坦距離(Levenshtein Distance),是針對(duì)二個(gè)字符串（例如英文字）的差異程度的量化量測(cè)，量測(cè)方式是看至少需要多少次的處理才能將一個(gè)字符串變成另一個(gè)字符串。

題目 input： str1 = "abc"? ? ? str2 = "yabd"

題目描述：

給出兩個(gè)字符串，求出最小的編輯距離，從str1 轉(zhuǎn)換到 str2。每個(gè)字符總共有三個(gè)轉(zhuǎn)換操作：插入，刪除，替換。

如圖所示，題目給出的例子的結(jié)果是2，如果需要將str1 轉(zhuǎn)換乘 str2， 我們可以看到，我們需要在字符串 abc 面前插入一個(gè)字符 y，同時(shí)需要將字符串a(chǎn)bc的c替換成字符d。這總共是執(zhí)行了兩步操作。所以結(jié)果2。

解決思路：

1. 畫(huà)二維圖（轉(zhuǎn)換成python就是一個(gè)二維數(shù)組）

畫(huà)一個(gè)二維圖去計(jì)算每一個(gè)字符需要轉(zhuǎn)換乘對(duì)應(yīng)字符所需要的距離是多少，注意：每個(gè)字符串前面都會(huì)有一個(gè)空字符。中間的空白空格需要填寫(xiě)的是，從str1中的一個(gè)子字符串 轉(zhuǎn)換到 str2的一個(gè)子字符串的最小的編輯。

2. 填寫(xiě)編輯距離

說(shuō)明： 圖中的位置我會(huì)用坐標(biāo)來(lái)表示（0，0），（1，0）代表坐標(biāo)的意思，黑色數(shù)字代表編輯距離

首先我們先從 行 開(kāi)始，

第二行的空字符串準(zhǔn)換到，第二列的空字符串是相等的，所以我們既不用 插入操作，也不用刪除操作，也不用替換操作，就能轉(zhuǎn)換到另一個(gè)。所以編輯距離是0。

再?gòu)倪@個(gè)空字符串轉(zhuǎn)換到 “ ” y 我們需要幾步呢？ 在空字符串添加里面加上一個(gè)“ ” y 我們就轉(zhuǎn)化成了“ ” y，我們執(zhí)行了一個(gè) 添加 的操作，所以編輯距離是1。

如果我們需要從空字符串轉(zhuǎn)換到 “ ” y a 我們需要幾步呢？在字符串 “ ” y 的基礎(chǔ)上再加一個(gè) a 我們就得到了? " " y a， 所以我們又執(zhí)行了一個(gè) 添加 操作，所以編輯距離在上一個(gè)添加的操作的基礎(chǔ)上增加了一個(gè) 1，總共是2，后面的以此類推。

然后我們開(kāi)始看 列

第三行的 ” “ a 轉(zhuǎn)換到 ” “ 我們需要執(zhí)行什么操作？刪除！，我們需要移除 a ，所以我們執(zhí)行一次移除的操作，因此編輯距離 + 1，0 + 1 = 1，所以編輯距離是1。下面的以此類推，” “ a b 轉(zhuǎn)換到 ” “ 我們需要執(zhí)行兩次移除操作，所以總共是 2 。。。

我們繼續(xù)填寫(xiě)

我們看到坐標(biāo)（1，-1）最小的編輯距離是1，” “ a 轉(zhuǎn)換到 ” “ y 我們只需要將 a 替換成 y。但是我們也可以先移除 （0，-1）a 坐標(biāo)， 然后增加（1，0）一個(gè) y，這樣的編輯距離是2。但是我們需要填入的是最小編輯距離，所以最終我們填入1。

然后我們移動(dòng)到坐標(biāo)（2，-1）我們可以看到這里的編輯距離是1，” “ a 轉(zhuǎn)換到 ” “ y a 我們需要添加一個(gè) y。如圖中綠色字的部分，因?yàn)閍 和 a是相同的，所以我們消除它，然后我們可以發(fā)現(xiàn)字符串只剩下了 str1 = “ ”，str2 = " " y，所以str1 到 str2 只需要 添加 y。所以編輯距離是1。

（3， -1）的編輯距離我們可以理解成：“ ” a 在轉(zhuǎn)成 “ ” y a 的基礎(chǔ)上插入了一個(gè) 字符b，所以可以看成是在 “ ” a 轉(zhuǎn)成 “ ” y a的基礎(chǔ)上加一個(gè)1，所以我們可以看出“ ” a轉(zhuǎn)成 “ ” y a b 的編輯距離是 1 + 1 = 2。后面的d也可以這樣理解，在 “ ” y a b 的基礎(chǔ)上再新增一個(gè) 1，所以（4， -1) 的編輯距離是3。

因此我們發(fā)現(xiàn)這個(gè)編輯距離填寫(xiě)的規(guī)律，如下圖所示坐標(biāo)（3，-1）的編輯距離是它 上方，左上方，左邊的最小數(shù) + 1（在兩個(gè)字符不一樣的情況下。坐標(biāo)（4， -1） 同理 min(上方，左上方，左邊）= min(4, 3, 2)? =? 2， 因此（4， -1）的編輯距離等于 2 + 1 = 3。但是在兩個(gè)字符串一樣的情況，如（2， -1），a 和 a是相同的所以不需要 +1，所以（2，-1）處的編輯距離 = min（2，1，1）= 1。接下來(lái)的方框大家都會(huì)填了吧？

最后是最終的二維表的所有編輯距離，我們最終的答案是取最右下角的數(shù)字，也就是2，所以我們最終的答案是2。

最后補(bǔ)充一點(diǎn)，左上角的編輯距離總是三個(gè)數(shù)中最小的

時(shí)間復(fù)雜度分析：

O(nm) time，因?yàn)槟阋⒌氖且粋€(gè)str1+1行 和 str2+1列的二維數(shù)組，并且填寫(xiě)里面每一個(gè)元素，并返回最后一個(gè)元素，所以程序的時(shí)間復(fù)雜度是和程序輸入str1和str2長(zhǎng)度有關(guān)。

空間復(fù)雜度分析：

我們需要開(kāi)辟一個(gè)str1+1行 和 str2+1列的二維數(shù)組取存儲(chǔ)我們的編輯距離，所以我們的空間復(fù)雜度也是O(nm)，當(dāng)然還有優(yōu)化的空間。

3. 代碼

接下來(lái)我們進(jìn)入代碼環(huán)節(jié)

這次代碼同樣也分成了，有注釋和和沒(méi)有注釋的版本，沒(méi)有注釋的請(qǐng)拉到最底部

第六行代碼生成list中的第一行是

[0,1,2,3,4,....] 因?yàn)榭兆址D(zhuǎn)換乘其他非空字符串就是一直加加加

列也同樣是0,1,2,3,4.... 列和行的長(zhǎng)度和輸入的str1 str2的長(zhǎng)度有關(guān)

沒(méi)有注釋的版本

恭喜你看到了這里！

接下來(lái)我們就來(lái)看看如何降低空間復(fù)雜度！

我們真的需要把整個(gè)n * m的list的空間開(kāi)辟出來(lái)嗎？我們最終使用的空間其實(shí)是藍(lán)色方框中的部分，我們實(shí)際算距離的部分只需要綠色方框和紅色方框。所以當(dāng)我們最終輸入的列越短，我們所需要的空間越少。因此我們?cè)谔幚磔斎氲臅r(shí)候我們可以將比較短的string輸入作為我們的列，比較長(zhǎng)的則作為我們的行。

所以我們最終的空間復(fù)雜度可以是O(min(n, m))

代碼：有注釋+無(wú)注釋

無(wú)注釋

Reference：代碼來(lái)自Algoexpert，以學(xué)習(xí)作為主要目的來(lái)分享的。