美文网首页动态规划
[Leetcode] 65. Edit Distance

[Leetcode] 65. Edit Distance

作者: 时光杂货店 | 来源:发表于2017-03-24 10:35 被阅读41次

    题目

    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

    相关文章

      网友评论

        本文标题:[Leetcode] 65. Edit Distance

        本文链接:https://www.haomeiwen.com/subject/bkixottx.html