[Leetcode] 65. Edit Distance

题目

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

解题之法

int minDistance(string word1, string word2) {
        if(word1 == word2) return 0;
         
        int m = word1.size();
        int n = word2.size();
         
        if(word1 == "")
        {
            return n;
        }
         
        if(word2 == "")
        {
            return m;
        }
         
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
         
        for(int i = 0; i < m + 1; ++i)
        {
            dp[i][n] = m - i;
        }
         
        for(int j = 0; j < n + 1; ++j)
        {
            dp[m][j] = n - j;
        }
         
         
        for(int i = m - 1; i >= 0; --i)
        {
            for(int j = n - 1; j >= 0; --j)
            {
                if(word1[i] == word2[j])
                {
                    dp[i][j] = dp[i+1][j+1];
                }
                else
                {
                    dp[i][j] = min(1 + dp[i][j+1], min(1 + dp[i+1][j], 1 + dp[i+1][j+1]));
                }
            }
        }
         
        return dp[0][0];
    }

这是由递归转化而来的，不过递归会TLE：

int minDistance(string word1, string word2) {
        if(word1 == word2) return 0;
         
        int m = word1.size();
        int n = word2.size();
         
        if(word1 == "")
        {
            return n;
        }
         
        if(word2 == "")
        {
            return m;
        }
         
        if(word1[0] == word2[0])
        {
            return minDistance(word1.substr(1), word2.substr(1));
        }
        else
        {
            return min(1 + minDistance(word1, word2.substr(1)), min(1 + minDistance(word1.substr(1), word2), 1 + minDistance(word1.substr(1), word2.substr(1))));
        }
 
    }

分析

Leetcode上好多动态规划的题 ， 一般碰到这样的题，先用递归把做出来，结果显然TLE。
既然能用递归，就肯定可以用动态规划，然后就把递归变成动态规划，变成动态规划后看能不能再优化空间，如果不能，就直接return了，如果能就优化，这个现在已经成为套路了。

另一种解法：

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n1 = word1.size(), n2 = word2.size();
        int dp[n1 + 1][n2 + 1];
        for (int i = 0; i <= n1; ++i) dp[i][0] = i;
        for (int i = 0; i <= n2; ++i) dp[0][i] = i;
        for (int i = 1; i <= n1; ++i) {
            for (int j = 1; j <= n2; ++j) {
                if (word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
                }
            }
        }
        return dp[n1][n2];
    }
};

分析：
这道题让求从一个字符串转变到另一个字符串需要的变换步骤，共有三种变换方式，插入一个字符，删除一个字符，和替换一个字符。根据以往的经验，对于字符串相关的题目十有八九都是用动态规划Dynamic Programming来解，这道题也不例外。这道题我们需要维护一个二维的数组dp，其中dp[i][j]表示从word1的前i个字符转换到word2的前j个字符所需要的步骤。那我们可以先给这个二维数组dp的第一行第一列赋值，这个很简单，因为第一行和第一列对应的总有一个字符串是空串，于是转换步骤完全是另一个字符串的长度。跟以往的DP题目类似，难点还是在于找出递推式，我们可以举个例子来看，比如word1是“bbc"，word2是”abcd“，那么我们可以得到dp数组如下：

Ø a b c d
Ø 0 1 2 3 4
b 1 1 1 2 3
b 2 2 1 2 3
c 3 3 2 1 2

我们通过观察可以发现，当word1[i] == word2[j]时，dp[i][j] = dp[i - 1][j - 1]，其他情况时，dp[i][j]是其左，左上，上的三个值中的最小值加1，那么可以得到递推式为：

dp[i][j] = / dp[i - 1][j - 1] if word1[i - 1] == word2[j - 1]
\ min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1 else