LeetCode72——Edit Distance-蒲公英云

LeetCode72——Edit Distance

十一月太忙，好一阵没写博客没刷题，现在事情忙完了，生活规律要逐步走入正轨。

-————————————————————————————————————————————————-

LeetCode72——Edit Distance

动态规划一直不是我的强项，但是这道题恰好不知道在哪里见到过。

首先说说动归方程：

dp[i][j]表示从word1的前i个字符( 0 ~ i - 1 )到word2的前j个字符( 0 ~ j - 1)的编辑过程中，需要的最少步数，那么：

如果 word1[i] = word2[j] 则 dp[i][j] = dp[i-1][j-1]

如果 word1[i] != word2[j] 则 dp[i][j] = min { dp[i-1][j] , dp[i][j-1], dp[i-1][j-1] } + 1

下面对上述动归进行解释

前一个条件比较好理解，下面对后一个三者的最小值+1，简单说明

假设word1的前i+1（下标从0~i）的子串为 “abcde”

假设word2的前j+1（下标从0~j）的子串为 “abcddgf”

现在word1[i] != word2[j] 即 ‘e’ != ‘f’

那么我们应当如何编辑？

分为三种情况：

1.从子串”abcd”编辑到子串”abcddg” 经过编辑后，word1变为”abcddge” （步数为dp[i-1][j-1]）

此时从word1编辑到word2只需要将’e’替换为’f’ （步数为1）

加起来就是：dp[i-1][j-1] + 1

2.从子串”abcd”编辑到子串”abcddgf”经过编辑后word1变成”abcddgfe” （步数为dp[i-1][j]）

此时从word1编辑到word2只需要将’e’删掉（步数为1）

加起来就是：dp[i-1][j] + 1

3.从子串”abcde”编辑到子串”abcddg”经过编辑后word1变成”abcddg” （步数为dp[i][j-1]）

此时从word1编辑到word2只需要插入字符’f’

加起来就是：dp[i][j-1] + 1

上述三种情况，事实上就完成了 Insert，Delete，Replace 三个操作

这三个操作需要的步数都是1，只需要比较上一次编辑（三种情况）到当前状态（只需要这三个操作之一就可以完成编辑）所需要的最小步数即可。

代码：

class Solution {
private:
    int myMin(int a, int b, int c)
    {
        if (b < a)
            a = b;
        if (c < a)
            a = c;
        return a;
    }
public:
    int minDistance(string word1, string word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        vector<vector<int>>dp(len1 + 1, vector<int>(len2 + 1));//dp
        //初始化
        for (int i = 0; i <= len1; i++)
        {
            dp[i][0] = i;
        }
        for (int j = 1; j <= len2; j++)
        {
            dp[0][j] = j;
        }
        //if  word1[i]==word2[j]
        //dp[i][j]  =  dp[i-1][j-1]
        //
        //
        for (int i = 1; i <= len1; i++)
        {
            for (int j = 1; j <= len2; j++)
            {
                if (word1[i-1] == word2[j-1])
                {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                else
                {
                    dp[i][j] = myMin(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1;
                }
            }
        }
        return dp[len1][len2];
    }
};