C++編輯距離問題

編輯距離，也被稱為 Levenshtein 距離，指兩個字符串之間互相轉(zhuǎn)換的最小修改次數(shù)，通常用于在信息檢索和自然語言處理中度量兩個序列的相似度。

如圖 14-27 所示，將 kitten 轉(zhuǎn)換為 sitting 需要編輯 3 步，包括 2 次替換操作與 1 次添加操作；將 hello 轉(zhuǎn)換為 algo 需要 3 步，包括 2 次替換操作和 1 次刪除操作。

圖 14-27   編輯距離的示例數(shù)據(jù)

編輯距離問題可以很自然地用決策樹模型來解釋。字符串對應(yīng)樹節(jié)點(diǎn)，一輪決策（一次編輯操作）對應(yīng)樹的一條邊。

如圖 14-28 所示，在不限制操作的情況下，每個節(jié)點(diǎn)都可以派生出許多條邊，每條邊對應(yīng)一種操作，這意味著從 hello 轉(zhuǎn)換到 algo 有許多種可能的路徑。

從決策樹的角度看，本題的目標(biāo)是求解節(jié)點(diǎn) hello 和節(jié)點(diǎn) algo 之間的最短路徑。

圖 14-28   基于決策樹模型表示編輯距離問題

1.   動態(tài)規(guī)劃思路

第一步：思考每輪的決策，定義狀態(tài)，從而得到 $dp$ 表

每一輪的決策是對字符串 $s$ 進(jìn)行一次編輯操作。

我們希望在編輯操作的過程中，問題的規(guī)模逐漸縮小，這樣才能構(gòu)建子問題。設(shè)字符串 $s$ 和 $t$ 的長度分別為 $n$ 和 $m$ ，我們先考慮兩字符串尾部的字符 $s[n?1]$ 和 $t[m?1]$ 。

• 若 $s[n?1]$ 和 $t[m?1]$ 相同，我們可以跳過它們，直接考慮 $s[n?2]$ 和 $t[m?2]$ 。
• 若 $s[n?1]$ 和 $t[m?1]$ 不同，我們需要對 $s$ 進(jìn)行一次編輯（插入、刪除、替換），使得兩字符串尾部的字符相同，從而可以跳過它們，考慮規(guī)模更小的問題。

也就是說，我們在字符串 $s$ 中進(jìn)行的每一輪決策（編輯操作），都會使得 $s$ 和 $t$ 中剩余的待匹配字符發(fā)生變化。因此，狀態(tài)為當(dāng)前在 $s$ 和 $t$ 中考慮的第 $i$ 和 $j$ 個字符，記為 $[i,j]$ 。

狀態(tài) $[i,j]$ 對應(yīng)的子問題：將 $s$ 的前 $i$ 個字符更改為 $t$ 的前 $j$ 個字符所需的最少編輯步數(shù)。

至此，得到一個尺寸為 $(i+1)\times (j+1)$ 的二維 $dp$ 表。

第二步：找出最優(yōu)子結(jié)構(gòu)，進(jìn)而推導(dǎo)出狀態(tài)轉(zhuǎn)移方程

考慮子問題 $dp[i,j]$ ，其對應(yīng)的兩個字符串的尾部字符為 $s[i?1]$ 和 $t[j?1]$ ，可根據(jù)不同編輯操作分為圖 14-29 所示的三種情況。

1. 在 $s[i?1]$ 之后添加 $t[j?1]$ ，則剩余子問題 $dp[i,j?1]$ 。
2. 刪除 $s[i?1]$ ，則剩余子問題 $dp[i?1,j]$ 。
3. 將 $s[i?1]$ 替換為 $t[j?1]$ ，則剩余子問題 $dp[i?1,j?1]$ 。

圖 14-29   編輯距離的狀態(tài)轉(zhuǎn)移

根據(jù)以上分析，可得最優(yōu)子結(jié)構(gòu)：$dp[i,j]$ 的最少編輯步數(shù)等于 $dp[i,j?1]$、$dp[i?1,j]$、$dp[i?1,j?1]$ 三者中的最少編輯步數(shù)，再加上本次的編輯步數(shù) $1$ 。對應(yīng)的狀態(tài)轉(zhuǎn)移方程為：

請注意，當(dāng) $s[i?1]$ 和 $t[j?1]$ 相同時，無須編輯當(dāng)前字符，這種情況下的狀態(tài)轉(zhuǎn)移方程為：

第三步：確定邊界條件和狀態(tài)轉(zhuǎn)移順序

當(dāng)兩字符串都為空時，編輯步數(shù)為 $0$ ，即 $dp[0,0]=0$ 。當(dāng) $s$ 為空但 $t$ 不為空時，最少編輯步數(shù)等于 $t$ 的長度，即首行 $dp[0,j]=j$ 。當(dāng) $s$ 不為空但 $t$ 為空時，等于 $s$ 的長度，即首列 $dp[i,0]=i$ 。

觀察狀態(tài)轉(zhuǎn)移方程，解 $dp[i,j]$ 依賴左方、上方、左上方的解，因此通過兩層循環(huán)正序遍歷整個 $dp$ 表即可。

2.   代碼實(shí)現(xiàn)

edit_distance.cpp

/* 編輯距離：動態(tài)規(guī)劃 */
int editDistanceDP(string s, string t) {
    int n = s.length(), m = t.length();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    // 狀態(tài)轉(zhuǎn)移：首行首列
    for (int i = 1; i <= n; i++) {
        dp[i][0] = i;
    }
    for (int j = 1; j <= m; j++) {
        dp[0][j] = j;
    }
    // 狀態(tài)轉(zhuǎn)移：其余行列
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s[i - 1] == t[j - 1]) {
                // 若兩字符相等，則直接跳過此兩字符
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                // 最少編輯步數(shù) = 插入、刪除、替換這三種操作的最少編輯步數(shù) + 1
                dp[i][j] = min(min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
            }
        }
    }
    return dp[n][m];
}

如圖 14-30 所示，編輯距離問題的狀態(tài)轉(zhuǎn)移過程與背包問題非常類似，都可以看作是填寫一個二維網(wǎng)格的過程。

圖 14-30   編輯距離的動態(tài)規(guī)劃過程

3.   空間優(yōu)化

由于 $dp[i,j]$ 是由上方 $dp[i?1,j]$、左方 $dp[i,j?1]$、左上方狀態(tài) $dp[i?1,j?1]$ 轉(zhuǎn)移而來，而正序遍歷會丟失左上方 $dp[i?1,j?1]$ ，倒序遍歷無法提前構(gòu)建 $dp[i,j?1]$ ，因此兩種遍歷順序都不可取。

為此，我們可以使用一個變量 leftup 來暫存左上方的解 $dp[i?1,j?1]$ ，從而只需考慮左方和上方的解。此時的情況與完全背包問題相同，可使用正序遍歷。

edit_distance.cpp

/* 編輯距離：空間優(yōu)化后的動態(tài)規(guī)劃 */
int editDistanceDPComp(string s, string t) {
    int n = s.length(), m = t.length();
    vector<int> dp(m + 1, 0);
    // 狀態(tài)轉(zhuǎn)移：首行
    for (int j = 1; j <= m; j++) {
        dp[j] = j;
    }
    // 狀態(tài)轉(zhuǎn)移：其余行
    for (int i = 1; i <= n; i++) {
        // 狀態(tài)轉(zhuǎn)移：首列
        int leftup = dp[0]; // 暫存 dp[i-1, j-1]
        dp[0] = i;
        // 狀態(tài)轉(zhuǎn)移：其余列
        for (int j = 1; j <= m; j++) {
            int temp = dp[j];
            if (s[i - 1] == t[j - 1]) {
                // 若兩字符相等，則直接跳過此兩字符
                dp[j] = leftup;
            } else {
                // 最少編輯步數(shù) = 插入、刪除、替換這三種操作的最少編輯步數(shù) + 1
                dp[j] = min(min(dp[j - 1], dp[j]), leftup) + 1;
            }
            leftup = temp; // 更新為下一輪的 dp[i-1, j-1]
        }
    }
    return dp[m];
}