首页 > 其他分享 >(55/60)两个字符串的删除操作、编辑距离

(55/60)两个字符串的删除操作、编辑距离

时间:2024-03-28 17:15:25浏览次数:22  
标签:string 55 60 int word1 word2 字符串 dp

两个字符串的删除操作

leetcode:583. 两个字符串的删除操作

动态规划

思路

  1. 先求最长子序长度
  2. 然后计算两个原字符串离最长子序长度差多少。

代码实现

class Solution {
public:
/* 
(之前搞错了)最长子序长度
word[0:i-1]和word2[0:j-1]的最长子序长dp[i][j]
if(word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
else dp[i][j] = max(dp[i-1][j],dp[i][j-1]);

初始化为0
*/
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1,0));
        for(int i = 1;i <= word1.size();i++){
            for(int j = 1;j <= word2.size();j++){
                if(word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
                else dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
                cout<<dp[i][j]<<' ';
            }
            cout<<endl;
        }

        return word1.size()+word2.size()-2*dp[word1.size()][word2.size()];
    }
};

编辑距离

leetcode:72. 编辑距离

动态规划

思路

增、删、替这三个操作在两个字符串之间是互逆的:

  1. 增、删是等效的(一个字符串增就是另一个字符串删);而替换就是dp[i-1][j-1] + 1

代码实现

class Solution {
public:
// word1[0:i-1]和word2[0:j-1]两个字符串相互转化的最少操作数为dp[i][j]
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size()+1,vector<int>(word2.size()+1,1));
        // 完整字符串<->空字符串 操作数为完整字符串的长度
        for(int i = 0;i <= word1.size();i++) dp[i][0] = i;
        for(int j = 0;j <= word2.size();j++) dp[0][j] = j;
        for(int i = 0;i <= word1.size();i++){
            for(int j = 0;j <= word2.size();j++){
                if(word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1];
                else dp[i][j] = min(dp[i-1][j]+1,min(dp[i][j-1]+1,dp[i-1][j-1]+1));
                // cout<<dp[i][j]<<' ';
            }
            // cout<<endl;
        }

        return dp[word1.size()][word2.size()];
    }
};

标签:string,55,60,int,word1,word2,字符串,dp
From: https://www.cnblogs.com/tazdingo/p/18102136

相关文章

  • (57/60)回文子串、最长回文子序列
    DP最后一集回文子串leetcode:647.回文子串动态规划代码实现classSolution{public:/*s[i:j]回文子串个数为dp[i][j]if(s[i]==s[j]){if(j-i<=1)dp[i][j]=true;elsedp[i][j]=dp[i+1][j-1];}全部初始化为0*/intcountSubstrings(strings)......
  • (58/60)每日温度、下一个更大元素Ⅰ
    每日温度leetcode:739.每日温度单调栈思路单调栈,存放元素下标。遍历一遍,每个元素和栈顶元素比较:<=栈顶元素,入栈>栈顶元素,result[st.top()]=i-st.top();弹出继续,直到遍历结束或<=栈顶元素代码实现classSolution{public:/*单调栈,存放元素下标遍历一遍,每个......
  • 补|(52/60)最长递增子序列、最长连续递增序列、最长重复子数组
    子序列问题最长递增子序列leetcode:300.最长递增子序列动态规划代码实现/*以nums[i]结尾的(含)递增子序列最长为dp[i]dp[i]由dp[0~i-1]的最大值推出if(nums[i]>nums[j])dp[i]=max(dp[i],dp[j]+1);//如果严格递增dp[0]=1;其余为0正序遍历*/classSol......
  • (60/60)last dance|柱状图中最大的矩形
    lastdance柱状图中最大的矩形leetcode:84.柱状图中最大的矩形单调栈思路和接雨水很类似,但需要首尾加0(尾0是为了触发计算,首0是为了避免首元素触发计算时没有left)注意点尾加0后还是要遍历到heights.size()-1,因为是以取出元素为基准计算的,而取出元素是当前遍历元素的上一......
  • (59/60)下一个更大元素Ⅱ、接雨水
    终于接到你下一个更大元素Ⅱleetcode:496.下一个更大元素I单调栈思路主要是循环数组的处理。直接等效为长度为2N,重复两遍的原数组即可,i<nums.size()变为i<2*nums.size()、i变为i%nums.size()。代码实现对每个元素都再遍历一遍原数组长度,,,时间复杂度O(N^2),超时了clas......
  • T555Pulse 555做为多谐振荡器的计算器A calculator for multi harmonic oscillators
    本软件很便宜,就是2包烟的钱。可以用来计算555的普通多谐震荡器电路的电阻、电容、周期、频率、高电平时间,低电平时间、占空比这类的东西的相互换算。Thissoftwareisverycheap,itcostsonly2packsofcigarettes.Itcanbeusedtocalculatethemutualconversionofr......
  • 08天【代码随想录算法训练营34期】第四章 字符串part02(KMP)
    KMP算法解决字符串匹配问题文本串aabaabaaf模式串aabaaf问:模式串是否在文本串中出现过?1)暴力解法,ptr指向文本串index0,遍历一遍发现不匹配,ptr再移向index1,遍历……依次重复,直到ptr指向32)KMP算法,ptr指向文本串index0,遍历到f发现不匹配,由于“aa”在字符串中index3和4时也出现......
  • 听劝!24 选错 660/880/1000的人,已经二战了
    25考研的备考形势,势必跟以前不一样了。24考完,大家都发现,没有一本习题册,覆盖了考试的所有知识点。主流的模拟卷,都没有达到24卷的难度。这就意味着:一本习题册不够了!刷主流模拟卷不够了!这会需要整个考研复习的安排,作一个很大的调整。如果你还在看24以前的学长规划,它就可能......
  • 算法打卡day28|贪心算法篇02|Leetcode 122.买卖股票的最佳时机 II、55. 跳跃游戏、45.
    算法题Leetcode122.买卖股票的最佳时机II题目链接:122.买卖股票的最佳时机II 大佬视频讲解:买卖股票的最佳时机II视频讲解 个人思路因为只有一只股票,且两天作一个交易单元,那每次只收集正利润就可以最终最多可以获取的利润,可以用贪心。解法贪心法从下图可以发......
  • 旷场实验KT-0860——观察研究实验动物神经精神变化
    旷场是观察研究实验动物神经精神变化、进入开阔环境后的各种行为,例如动物对新开阔环境的恐惧而主要在周边区域活动,在中间区域活动较少,但动物的探究特性又促使其产生在中间区域活动的动机,也可观察由此而产生的焦虑心理。兴奋药可以明显增加自主的活动而减少探究行为,在统一些剂......