题解 | #编辑距离(二)#
编辑距离(二)
https://www.nowcoder.com/practice/05fed41805ae4394ab6607d0d745c8e4
动态规划
思路和编辑距离(一)基本相同，两者学会一个就能互通
状态转移方程分析：
dp[i][j]表示将str1的前i个字符转化成str2的前j个字符所需的操作数
当str1[i-1] = str2[j-1] 时
此时状态转移方程为：dp[i][j]=dp[i-1][j-1] //这步简单不多解释
当str1[i-1] != str2[j-1] 时，要分情况分析
- 插入： dp[i][j-1] + ic 表示在str1的前i位转化成str2的前j-1个位 代价最小的基础上，将str2的第j位添加到str1上
- 删除： dp[i-1][j] + dc 表示在str1的前i-1位转化成str2的前j个位 代价最小的基础上，将str1的第i位删除
- 修改： dp[i-1][j-1] + dc 表示在str1的前i-1位转化成str2的前j-1个位 代价最小的基础上，修改str1的第i位使其等于str2的第j位
时间复杂度O(n*m) 空间复杂度O(n*m)
class Solution {
public:
int minEditCost(string str1, string str2, int ic, int dc, int rc) {
int len1=str1.size();
int len2=str2.size();
//dp[i][j]表示将str1[i]变化成str2[j]所需要的最小操作数
vector<vector<int>> dp(len1+1,vector<int>(len2+1,0));
for(int i=0;i<=len1;i++){
dp[i][0]=i*dc;//第二个字符串为空时，第一个字符串每多一位，第一个字符串删除一位
}
for(int i=0;i<=len2;i++){
dp[0][i]=i*ic;//第一个字符串为空时，第二个字符串每多一位，第一个字符串添加一位
}
for(int i=1;i<=len1;i++){
for(int j=1;j<=len2;j++){
if(str1[i-1]==str2[j-1]){
dp[i][j]=dp[i-1][j-1];//当str1的第i个位置的元素和str2第j个位置的元素相同时
}else{//不同时分情况，要选择最小的情况
int ins=dp[i][j-1]+ic;//表示在str1的前i个字符变成str2的前j-1个字符操作数最小的基础上，把str2的第j位字符添加到str1上
int del=dp[i-1][j]+dc;//表示在str1的前i-1个字符变成str2的前j个字符操作数最小的基础上，删除str1的第i个字符
int rep=dp[i-1][j-1]+rc;//表示在str1的前i-1个字符变成str2前j-1个字符操作数最小的基础上修改str1的第i位使其等于str2的第j位
dp[i][j]=min(ins,min(del,rep));
}
}
}
return dp[len1][len2];
}
};
，那么有还在纯聊经验聊技术的群吗
快手成长空间 247人发布
