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

題意

對于給定兩個單詞word1和word2驶忌，你可以對word1進行以下3種操作：

a） 插入一個字母
b） 刪除一個字母
c） 替換一個字母

請計算將word1變換成word2的最少操作數(shù)逃延。

分析

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

編輯距離
兩個字符串的各種對齊所可能具有的最小代價诫肠。
即司澎，它可以被視為將一個字符串變換為另一個字符串所需最小編輯操作，包括插入栋豫、刪除以及字符替換的次數(shù)挤安。

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

如何劃分子問題

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

三種對齊方式（- 代表一個空隙）

對空格及編輯代價的解釋
當兩個字符串不相同時丛肢，想要對齊它們围肥，可以寫成如下形式（以SNOWY和SUNNY為例）：

代價為3

或

代價為5

其中，-表示一個空隙摔踱，對齊時虐先，可以將它隨意插入到每個字符串中。對于一種對齊方式派敷，其代價是指上下字符串對應字母不相同的列數(shù)蛹批。而編輯距離是指兩個字符串的各種對齊所可能具有的最小代價撰洗。

利用二維矩陣

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

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

該算法的偽代碼：

偽代碼

參考資料
《算法概論》/《Algorithm》 - Sanjoy Dasgupta著猪勇；
第六章 動態(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()];
    }
};