题解 | #编辑距离(一)#

一.题目简介

给定两个字符串str1和str2，可以进行插入、删除、替换，返回将str1编辑成str2的最小操作次数。

二.算法一(动态规划)

(1)动态规划：$dp[i][j]dp[i][j]$表示str1的前i个字符编辑成str2的前j个字符需要的最小操作数

(2)边界处理：从表格可以看出来：

1.求第一行dp[0][j]，dp[0][j]=j;

2.求第一列dp[i][0]，dp[i][0]=i;

(3)状态转移：

1.当i字符等于j字符的时候：dp[i][j]=dp[i-1][j-1]相等不需要操作

2.当i字符不等于j字符的时候：dp[i][j]的值等于插入、替换和删除的最大值

插入：dp[i][j-1]+1; 将i个字符串转变为前j-1个字符串在插入第j个字符

删除：dp[i-1][j]+1;  将i-1个字符串转换为前j个字符串删除第i个字符

替换：dp[i-1][j-1]+1; i-1个编辑成j-1个字母，再将i替换成j

下面是完整代码：

class Solution {
public:
    int editDistance(string str1, string str2) {
        int m = str1.size();
        int n = str2.size();
        int dp[5005][5005]; //刚开始对边界的初始化
        for(int i=0;i<=m;i++) dp[i][0]=i;
        for(int j=0;j<=n;j++) dp[0][j]=j;
        for(int i=1; i<=m; i++){
            for(int j=1; j<=n; j++){
                int a=dp[i][j-1]+1;//插入
                int b=dp[i-1][j]+1;//删除
                int c=dp[i-1][j-1];//替换
                if(str1[i-1]!=str2[j-1]) c+=1;
                dp[i][j]=min(a, min(b, c));
            }
        }
        return dp[m][n];
    }
};

时间复杂度：$O(n^2)O(n^\{2\})$ 需要进行两次遍历

空间复杂度：$O(n^2)O(n^\{2\})$需要额外开辟二维数组

三.算法(利用状态压缩优化动态规划)

我们可以发现当前状态仅仅和上一个状态有关，所以我们可以利用状态压缩来解决，在空间上完成了优化，下面是完整代码：

class Solution {
public:
    int editDistance(string str1, string str2) {
        int m = str1.size();
        int n = str2.size();
        int dp[2][5005];
        for(int i=0; i<=m; i++){
            for(int j=0;j<=n;j++){
                //由于状态是压缩的所以每一次都要对其进行初始化
                dp[i%2][j]=0x3f3f3f3f;
            }
            for(int j=0; j<=n; j++){
                if(i*j==0){
                    dp[i%2][j]=i+j;
                } else {
                   if(str1[i-1] == str2[j-1]){ // 匹配
                        dp[i%2][j] = min(dp[i%2][j],dp[(i-1)%2][j-1]);
                    }else{
                       //状态转移当前状态之和上一次的状态有关
                        dp[i%2][j] = min(dp[i%2][j],dp[(i-1)%2][j]+1); // 删除
                        dp[i%2][j] = min(dp[i%2][j],dp[i%2][j-1]+1); // 增加
                        dp[i%2][j] = min(dp[i%2][j],dp[(i-1)%2][j-1]+1); // 修改
                    }
                }
            }
        }
        return dp[m%2][n];
    }
};

时间复杂度: $O(n^2)O(n^2)$ 进行了双重循环。

空间复杂度: $O(n)O(n)$ 进行状态压缩，空间复杂度降低了。