LeetCode #72: Edit Distance

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的最少操作数。

分析

此题是一个非常典型动态规划问题，里面涉及到一个概念（即本题的题目）：编辑距离。

编辑距离
两个字符串的各种对齐所可能具有的最小代价。
即，它可以被视为将一个字符串变换为另一个字符串所需最小编辑操作，包括插入、删除以及字符替换的次数。

用动态规划思想解决

如何划分子问题

• 有两个字符串x[1...n]，y[1...m]
• 考虑两个字符串的长度各自为i和j的前缀x[1...i]，y[1...j]
• 对于x[i]和y[j]的最佳对齐（最佳对齐是指，为得到全局最优解而取的局部最优解），有以下可能的三种情况：

三种对齐方式（- 代表一个空隙）

对空格及编辑代价的解释
当两个字符串不相同时，想要对齐它们，可以写成如下形式（以SNOWY和SUNNY为例）：

代价为3
或
代价为5
其中，-表示一个空隙，对齐时，可以将它随意插入到每个字符串中。对于一种对齐方式，其代价是指上下字符串对应字母不相同的列数。而编辑距离是指两个字符串的各种对齐所可能具有的最小代价。

利用二维矩阵

以exponential和polynomial为例，结合我们上面谈到的对两个字符串中的两个字符进行对齐，算出其代价，可得到如下的二维矩阵：

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

该算法的伪代码：

伪代码

参考资料
《算法概论》/《Algorithm》 - Sanjoy Dasgupta著；
第六章 动态规划：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()];
    }
};