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

编辑距离(二)

https://www.nowcoder.com/practice/05fed41805ae4394ab6607d0d745c8e4

1.经典动态规划解法

设s[k]为s[0...k]的子串,那么cost[i][j]为从s1[i]编辑为s2[j]的代价。

  • 如果s1[i] == s2[j], 那么cost[i][j] = cost[i-1][j-1];
  • 否则有三种方法可以完成这一次编辑::
    • 用cost[i-1][j-1]的代价将s1[i-1]编辑为s2[j-1],再将s1[i]替换为s[j],即cost[i][j-1] + rc;

    • 用cost[i][j-1]的代价将s1[i]编辑为s2[j-1],再插入一个s2[j]字符, 即cost[i][j-1] + ic;

    • 用cost[i-1][j]的代价将s1[i-1]编辑为s2[j], 再删除s1[i]字符,即cost[i-1][j] + dc;

    • 所以最小编辑代价,cost[i][j] = min(cost[i-1][j-1] + rc, cost[i][j-1] + ic, cost[i-1][j] + dc);
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) {
        // write code here 
        int n1 = str1.size();
        int n2 = str2.size();
        vector<vector<int>> cost(n1 + 1, vector<int>(n2 + 1 ));
        for(int i = 0; i < n1 + 1; ++i){
            cost[i][0] = i*dc;
        }
        for(int j = 0; j < n2 + 1; ++j){
            cost[0][j] = j*ic;
        }
        
        for(int i = 1; i < n1 + 1; ++i){
            for(int j = 1; j < n2 + 1; ++j){
                if(str1[i-1] == str2[j-1]){
                    cost[i][j] = cost[i-1][j-1];
                }else{
                    cost[i][j] = min(min(cost[i-1][j] + dc, cost[i][j-1] + ic),  cost[i-1][j-1] + rc);
                }
            }
        }
        return cost[n1][n2];
    }
};

分析: 时间复杂度:O(mn),空间复杂度O(mn)

2. 空间优化

每一个位置[i,j]只与[i-1,j-1]、[i-1,j]、[i,j-1]三个位置有关。[i-1,j-1]为左上对角线上的位置,只需用一个变量pre保存;[i-1][j]为当前列的上一行的位置,[i][j-1]当前行的前一列的位置,只需用一个数组保存。

行i从上至下扫描;列j从左到右扫描。使用cost[j]保存扫描到j列时的编辑代价,此时,cost[0...j]为当前行更新到第j列已更新的值,cost[j+1:n2]为上一行相应位置的代价,还需要更新。

  • cost[j]的初始值为空串“”编辑为s2[j]的代价,即ic*j;
  • cost[0]为将s1[i]编辑为空串“”的代价,即dc*i。
  • pre的初值为cost[0]
  • 用tmp保存cost[j]更新前的值(即上一行的cost[j]),用作下一列更新的pre值。

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) {
        // write code here 
        int n1 = str1.size();
        int n2 = str2.size();
        vector<int> cost(n2+1);
        for(int j = 1; j < n2 + 1; j++){
            cost[j] = j*ic;
        }
        for(int i = 1; i < n1 + 1; i++){
            int pre = cost[0];
            cost[0] = dc*i;
            for(int j = 1; j < n2 + 1; j++){
                int tmp = cost[j]; //保存更新cost[j]之前的值,用作下一次更新的pre。
                if(str1[i-1] == str2[j-1]){
                    cost[j] = pre;
                }else{
                    cost[j] = min(cost[j-1] + ic, cost[j] + dc);
                    cost[j] = min(cost[j], pre + rc);
                }
                pre = tmp;
            }
        }
        
        return cost[n2];
    }
};

分析:时间复杂度O(nm),空间复杂度O(n).

全部评论

相关推荐

07-14 12:29
门头沟学院 Java
后端岗,实习三周感觉有点想跑路了,担心秋招被拉黑,有没有佬是字节HR知道情况的
从零开始的转码生活:你实习三周都想跑路,将来拿到offer真的愿意在这干十几二十年吗
投递字节跳动等公司10个岗位
点赞 评论 收藏
分享
Twilight_m...:表格简历有点难绷。说说个人看法: 1.个人基本情况里好多无意义信息,什么婚姻状况、健康状况、兴趣爱好、户口所在地、身份证号码、邮政编码,不知道的以为你填什么申请表呢。 2.校内实践个人认为对找工作几乎没帮助,建议换成和测开有关的项目,实在没得写留着也行。 3.工作经历完全看不出来是干什么的,起码看着和计算机没啥关系,建议加强描述,写点你在工作期间的实际产出、解决了什么问题。 4.个人简述大而空,看着像AI生成,感觉问题最大。“Python,C,C++成为我打造高效稳定服务的得力工具”、“我渴望凭借自身技术知识与创新能力,推动人工智能技术的应用发展,助力社会实现智能化转型”有种小学作文的美感。而且你确定你个人简述里写的你都会嘛?你AI这块写的什么“深入研究”,发几篇顶会的硕博生都不一定敢这么写。而且你AI这块的能力和软测也完全无关啊。个人简述建议写你对哪些技术栈、哪些语言、哪些生产工具的掌握,写的有条理些,而且最好是和测开强相关的。
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务