用js實作編輯距離算法（Edit Distance）

題目

lintcode題目連結

給出兩個單詞word1和word2，計算出将word1 轉換為word2的最少操作次數。

你總共三種操作方法：

插入一個字元

删除一個字元

替換一個字元

解析

編輯無非就是三種情況，字元的插入、删除以及編輯：

插入一個字元為進行了一次操作，如：

fat

->

fait

;

删除一個字元也視為進行一次操作，如：

haven

->

have

;

替換字元也視為進行一次操作，如：

let

->

lit

。

這個算法的原理不太好了解，但放到矩陣中實作的過程很簡單，我們把兩個字元串放到矩陣裡進行解析，這裡用到了動态規劃：

在相同位置上兩個字元串不同:cost=1；反則為0

matrix[m][n]=Math.min(matrix[m-1][n]+1,matrix[m][n-1]+1,matrix[m-1][n-1]+cost)
           

其中

matrix[m-1][n]+1

代表删除操作，

matrix[m][n-1]+1

代表新增，

matrix[m-1][n-1]+cost

代表字元的替換，然後求出他們三個值的最小值。

圖解

我們舉個例子，看下圖解：

計算

ivan1

和

ivan2

兩個字元串的最小操作次數：

1.矩陣初始化

先建構一個首行首列都從0增長的矩陣，長度為

(s1.length+1)*(s2.length+1)

。

2.計算最小值

之後開始對比兩個字元串的每個位置，按照上一節的公式取最小值。

3.類推完成，取右下角的值，即為最短編輯距離

代碼

function minDistance(s1, s2) {
    const len1 = s1.length
    const len2 = s2.length

    let matrix = []

    for (let i = ; i <= len1; i++) {
        // 構造二維數組
        matrix[i] = new Array()
        for (let j = ; j <= len2; j++) {
            // 初始化
            if (i == ) {
                matrix[i][j] = j
            } else if (j == ) {
                matrix[i][j] = i
            } else {
                // 進行最小值分析
                let cost = 
                if (s1[i - ] != s2[j - ]) { // 相同為0，不同置1
                    cost = 
                }
                const temp = matrix[i - ][j - ] + cost

                matrix[i][j] = Math.min(matrix[i - ][j] + , matrix[i][j - ] + , temp)
            }
        }
    }
    return matrix[len1][len2] //傳回右下角的值
}

minDistance('jary','jerry') // 2
           

參考文檔

1. 編輯距離算法（Edit Distance）