编辑距离(二)（动态规划）

题意

给定两个字符串,把字符串str1编辑为str2的最小代价,其中插入(ic),删除(dc)和替换(rc)代价分别为给定常数

思路分析

顺序性无关证明

设对str1有一系列操作,

对于一个被增加的字符,一定不会被删除和被修改

对于一个被删除的字符,一定不会被增加和被修改

对一个修改出的字符,一定不会被增加和删除

这些操作相对于最终结果来说,调整顺序对结果无影响.

也就是不妨设所有操作从左到右依次执行

上一步关系

那么如果我们通过操作让str1和str2相等了

按照下标考虑,如果str1最后一个字符和str2一致, 那么不操作的代价最低,如何把str1[:-1]变为str2[:-1]

如果str1最后一个字符和str2不同

那么有3种方案,

删除最后一个字符,考虑如何把str1[:-1]变为str2
修改最后一个字符,考虑如何把str1[:-1]变为str2[:-1]
增加一个字符,考虑如何把str1变为str2[:-1]

转换成表达式

把上面文字描述的关系转换成表达式

if(str1[i] == str2[j])
	dp[i][j] = dp[i-1][j-1];
else{
	dp[i][j] = min(
		dp[i-1][j] + delete cost,
		dp[i-1][j-1] + replace cost,
		dp[i][j-1] + insert cost
	);
}

边界处理

这里主要的边界是把有长度的str1转换成空字符串,也就是删去所有的代价

for(int i = 0;i < str1.size();i++){
    dp[i][0] = dc * i; // str2长度为0
}

另一个是未计算过的值,因为要求最小值,所以未计算的值设置成无限大INF

样例数据举例

以样例数据1: str1="abc",str2="adc",ic=5,dc=3,rc=2建立表

alt

题解

所以整合上面的内容

class Solution {
public:
    /**
     * min edit cost
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @param ic int整型 insert cost
     * @param dc int整型 delete cost
     * @param rc int整型 replace cost
     * @return int整型
     */
    int minEditCost(string str1, string str2, int ic, int dc, int rc) {
        const int INF = 0x3f3f3f3f;
        vector<vector<int> > dp(str1.size()+1,vector<int>(str2.size()+1,INF)); // 记录最小代价
        for(int i = 0;i < str1.size();i++){
            dp[i][0] = dc * i; // str2长度为0
            for(int j = 0;j < str2.size();j++){
                if(str1[i] == str2[j]){ // 相等时
                    dp[i+1][j+1] = dp[i][j];
                }else{
                    dp[i+1][j+1] = min(
                        dp[i][j+1] + dc, // 删
                        min( dp[i][j] + rc, //改
                        dp[i+1][j] + ic ) // 增
                    );
                }
            }
        }
        return dp[str1.size()][str2.size()];
    }
};

复杂度分析

空间复杂度: 状态数量是两个字符串长度之积，所以空间复杂度为 $O (n^{2})$

时间复杂度: 状态转移代价是常数代价,所以时间复杂度为 $O (n^{2})$

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