题意

字符串A最少需要多少次, 插入/删除/修改 能变成字符串B

限制,两个字符串长度均不超过$500500$

方法

递推+状态

设计状态 dp[i][j] 表示,地一个字符串的前i个最少操作dp[i][j]次能变成第二个字符串前j

那么有状态转移

A[i]=B[j]时,对应位置字符相等,直接匹配,dp[i][j] = dp[i-1][j-1]

A[i]!=B[j]时,可以采取修改,删除和插入三种方法,dp[i][j] = min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1

以样例数据"nowcoder","new"为例

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str1 string字符串 
     * @param str2 string字符串 
     * @return int整型
     */
    int editDistance(string str1, string str2) {
        // write code here
        vector<vector<int> > dp(str1.length()+1,vector<int>(str2.length()+1,0x3f3f3f3f));
        for(int i = 0;i<= str1.length();i++){
            for(int j=0;j<= str2.length();j++){
                if(i*j==0){
                    dp[i][j] = i+j;
                }else{
                    if(str1[i-1] == str2[j-1]){ // 匹配
                        dp[i][j] = min(dp[i][j],dp[i-1][j-1]);
                    }else{
                        dp[i][j] = min(dp[i][j],dp[i-1][j]+1); // 删除
                        dp[i][j] = min(dp[i][j],dp[i][j-1]+1); // 增加
                        dp[i][j] = min(dp[i][j],dp[i-1][j-1]+1); // 修改
                    }
                }
            }
        }
        return dp[str1.length()][str2.length()];
    }
};

复杂度分析

因为两个字符串的长度可能不同,设字符串A的长度为$mm$,字符串B的长度为$nn$.

时间复杂度: 时间代价为空间代价乘上转移代价,为$O(nm)O(nm)$

空间复杂度: 空间复杂度为设计的状态大小,为$O(nm)O(nm)$

滚动数组空间优化

注意到状态转移每次只依赖于上一层状态, 所以状态只用保存两层

我们通过把坐标mod 2来实现滚动数组

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str1 string字符串 
     * @param str2 string字符串 
     * @return int整型
     */
    int editDistance(string str1, string str2) {
        // write code here
        vector<vector<int> > dp(2,vector<int>(str2.length()+1,0x3f3f3f3f));
        for(int i = 0;i<= str1.length();i++){
            for(int j=0;j<= str2.length();j++){ // 因为是复用空间,记得清理初始化
                dp[i%2][j] = 0x3f3f3f3f;
            }
            for(int j=0;j<= str2.length();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[str1.length()%2][str2.length()];
    }
};

复杂度分析

因为两个字符串的长度可能不同,设字符串A的长度为$mm$,字符串B的长度为$nn$.

时间复杂度: 时间代价为状态数量乘上转移代价,为$O(nm)O(nm)$

空间复杂度: 状态数量没有变,但是程序复用了内存空间,为$O(n)O(n)$