LeetCode 72.编辑距离(动态规划)

题目描述:(来自LeetCode官网)

LeetCode 72.编辑距离(动态规划)

解题思路:
将word1变成word2,对于每个字符,我们可能进行的操作有三种,增删改,但去暴力枚举每一个的话,时间复杂度过高,用动态规划去优化。

对于状态规划,要确定两点,状态表示和状态计算

首先:状态表示

        (1)确定维度

        一般先从一维开始考虑,维数越高意味着复杂度可能相应的加一个维度,这道题要用状态表示两个字符串,一维很难进行两个字符串的判断,因此用二维来表示。f[i][j]

        (2)确定状态代表的集合和属性

        在这里,我们用f[i][j]表示将所有word1[1~i]变成word2[1~j]的操作方式,而最短编辑距离即在这所有的操作里,找一个操作数最小的,故属性就是求最小值

其次:状态计算

        (1)增:当增加一个元素可以使word1[1~i]变成word2[1~j],说明在此之前要满足word1[1~i]==word2[1~j-1],这样在增加一个元素之后,才能使word1[1~i]==word2[1~j],所以f[i][j]=f[i][j-1]+1;

        (2)删:当删除一个元素可以使word1[1~i]变成word2[1~j],说明在此之前要满足word1[1~i-1]==word2[1~j],这样在删除一个元素怒之后,才能使word1[1~i]==word2[1~j],所以f[i][j]=f[i-1][j]+1;

        (3)改:这时分两种情况,如果word1[i]=word2[j],则不需要修改了,否则在修改完之后可以使word1[1~i]变成word2[1~j],那么在此之前要满足word1[1~i-1]==word2[1~j-1],所以f[i][j]=word1[i]=word2[j]==0?f[i-1][j-1]+0:f[i-1][j-1]+1

最后,要考虑边界问题

        (1)一般就是处理下标为0的情况,在这道题中,f[i][0]=i,因为这表示word1[1~i]变成word2[0],就是变成空,那就只能是删除i个元素,就是i次操作,同理f[0][i]=i表示word1初始为空,变成word2长度为i,就是添加i次。

        (2)求最大最小值初始化数组的问题,一般再求最大值的时候,我们要将数组初始化为无穷小的数,而求最小值的时候,我们要将数组初始化为无穷大的数,但因为本题最小的数就是数组的初值,不用初始化

代码实现C++:

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n1=word1.length(),n2=word2.length();
        int f[505][505];
        if(n1==0) return n2;
        if(n2==0) return n1;
        for(int i=0;i<=n1;i++) f[i][0]=i;
        for(int j=0;j<=n2;j++) f[0][j]=j;
        for(int i=1;i<=n1;i++){
            for(int j=1;j<=n2;j++){
                f[i][j]=min(f[i][j-1]+1,f[i-1][j]+1);
                if(word1[i-1]==word2[j-1]) f[i][j]=min(f[i][j],f[i-1][j-1]);
                else f[i][j]=min(f[i][j],f[i-1][j-1]+1);
            }
        }
        return f[n1][n2];
    }
};
上一篇:CentOS安装docsify


下一篇:Linux应用编程实现简单队列功能-改进