Problem

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

題意

對(duì)于給定兩個(gè)單詞word1和word2，你可以對(duì)word1進(jìn)行以下3種操作：

a） 插入一個(gè)字母
b） 刪除一個(gè)字母
c） 替換一個(gè)字母

請(qǐng)計(jì)算將word1變換成word2的最少操作數(shù)。

分析

此題是一個(gè)非常典型動(dòng)態(tài)規(guī)劃問題，里面涉及到一個(gè)概念（即本題的題目）：編輯距離。

編輯距離
兩個(gè)字符串的各種對(duì)齊所可能具有的最小代價(jià)。
即，它可以被視為將一個(gè)字符串變換為另一個(gè)字符串所需最小編輯操作，包括插入、刪除以及字符替換的次數(shù)。

用動(dòng)態(tài)規(guī)劃思想解決

如何劃分子問題

• 有兩個(gè)字符串x[1...n]，y[1...m]
• 考慮兩個(gè)字符串的長(zhǎng)度各自為i和j的前綴x[1...i]，y[1...j]
• 對(duì)于x[i]和y[j]的最佳對(duì)齊（最佳對(duì)齊是指，為得到全局最優(yōu)解而取的局部最優(yōu)解），有以下可能的三種情況：

三種對(duì)齊方式（- 代表一個(gè)空隙）

對(duì)空格及編輯代價(jià)的解釋
當(dāng)兩個(gè)字符串不相同時(shí)，想要對(duì)齊它們，可以寫成如下形式（以SNOWY和SUNNY為例）：

代價(jià)為3

或

代價(jià)為5

其中，-表示一個(gè)空隙，對(duì)齊時(shí)，可以將它隨意插入到每個(gè)字符串中。對(duì)于一種對(duì)齊方式，其代價(jià)是指上下字符串對(duì)應(yīng)字母不相同的列數(shù)。而編輯距離是指兩個(gè)字符串的各種對(duì)齊所可能具有的最小代價(jià)。

利用二維矩陣

以exponential和polynomial為例，結(jié)合我們上面談到的對(duì)兩個(gè)字符串中的兩個(gè)字符進(jìn)行對(duì)齊，算出其代價(jià)，可得到如下的二維矩陣：

其中，(i, j) = min(1 + (i - 1, j), 1 + (i, j - 1), diff(w1[i], w2[j]) + (i - 1, j - 1))

該算法的偽代碼：

偽代碼

參考資料
《算法概論》/《Algorithm》 - Sanjoy Dasgupta著；
第六章 動(dòng)態(tài)規(guī)劃：6.3 編輯距離

Code

//Runtime: 12ms
class Solution {
public:
    int diff(char a, char b){
        return !(a == b);
    }
    int min(const int& a, const int& b, const int& c){
        int tmp = a < b ? a : b;
        return (tmp < c ? tmp : c);
    }

    int minDistance(string word1, string word2) {
        if(word1.size() == 0 && word2.size() == 0)
            return 0;
        if (word1.size() == 0 && word2.size() != 0)
            return word2.size();
        if (word2.size() == 0 && word1.size() != 0)
            return word1.size();
        
        vector<vector<int>> matrix;
        matrix.resize(word1.size() + 1);
        for (int i = 0; i <  word1.size(); i++)
            matrix[i].resize(word2.size() + 1);
        matrix[0][0] = 0;

        for (int i = 1; i < word1.size() + 1; i++)
            matrix[i][0] = matrix[i - 1][0] + 1;
        for (int j = 1; j < word2.size() + 1; j++)
            matrix[0][j] = matrix[0][j - 1] + 1;

        for (int i = 1; i < word1.size() + 1; i++)
            for (int j = 1; j < word2.size() + 1; j++){
                matrix[i][j] = min(1 + matrix[i - 1][j], 
                                   1 + matrix[i][j - 1], 
                                   diff(word1[i - 1], word2[j - 1]) + matrix[i - 1][j - 1]);
            }
        
        return matrix[word1.size()][word2.size()];
    }
};