训练营第四十二天| 583. 两个字符串的删除操作72. 编辑距离647. 回文子串516.最长回文子序列

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

力扣题目链接(opens new window)

给定两个单词 word1 和 word2,找到使得 word1 和 word2 相同所需的最小步数,每步可以删除任意一个字符串中的一个字符。

示例:

  • 输入: "sea", "eat"
  • 输出: 2
  • 解释: 第一步将"sea"变为"ea",第二步将"eat"变为"ea"

思路

动态规划一

本题和动态规划:115.不同的子序列 (opens new window)相比,其实就是两个字符串都可以删除了。动规五部曲,分析如下:

  1. 确定dp数组(dp table)以及下标的含义

dp[i][j]:以i-1为结尾的字符串word1,和以j-1位结尾的字符串word2,想要达到相等,所需要删除元素的最少次数。

这里dp数组的定义有点点绕,大家要撸清思路。

  1. 确定递推公式
  • 当word1[i - 1] 与 word2[j - 1]相同的时候
  • 当word1[i - 1] 与 word2[j - 1]不相同的时候

当word1[i - 1] 与 word2[j - 1]相同的时候,dp[i][j] = dp[i - 1][j - 1];

当word1[i - 1] 与 word2[j - 1]不相同的时候,有三种情况:

情况一:删word1[i - 1],最少操作次数为dp[i - 1][j] + 1

情况二:删word2[j - 1],最少操作次数为dp[i][j - 1] + 1

情况三:同时删word1[i - 1]和word2[j - 1],操作的最少次数为dp[i - 1][j - 1] + 2

那最后当然是取最小值,所以当word1[i - 1] 与 word2[j - 1]不相同的时候,递推公式:dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1});

因为 dp[i][j - 1] + 1 = dp[i - 1][j - 1] + 2,所以递推公式可简化为:dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);

这里可能不少录友有点迷糊,从字面上理解 就是 当 同时删word1[i - 1]和word2[j - 1],dp[i][j-1] 本来就不考虑 word2[j - 1]了,那么我在删 word1[i - 1],是不是就达到两个元素都删除的效果,即 dp[i][j-1] + 1。

  1. dp数组如何初始化

dp[i][0]:word2为空字符串,以i-1为结尾的字符串word1要删除多少个元素,才能和word2相同呢,很明显dp[i][0] = i。

2 .确定遍历顺序

从递推公式 dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1]) + 1); 和dp[i][j] = dp[i - 1][j - 1]可以看出dp[i][j]都是根据左上方、正上方、正左方推出来的。

所以遍历的时候一定是从上到下,从左到右,这样保证dp[i][j]可以根据之前计算出来的数值进行计算。

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 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 = 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];
                } else {
                    dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
                }
            }
        }
        return dp[word1.size()][word2.size()];
    }
};

  • 时间复杂度: O(n * m)
  • 空间复杂度: O(n * m)

#动态规划二

本题和动态规划:1143.最长公共子序列 (opens new window)基本相同,只要求出两个字符串的最长公共子序列长度即可,那么除了最长公共子序列之外的字符都是必须删除的,最后用两个字符串的总长度减去两个最长公共子序列的长度就是删除的最少步数。

代码如下:

class Solution {
public:
    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]);
            }
        }
        return word1.size()+word2.size()-dp[word1.size()][word2.size()]*2;
    }
};

  • 时间复杂度: O(n * m)
  • 空间复杂度: O(n * m)

72. 编辑距离

力扣题目链接(opens new window)

给你两个单词 word1 和 word2,请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作:

  • 插入一个字符

  • 删除一个字符

  • 替换一个字符

  • 示例 1:

  • 输入:word1 = "horse", word2 = "ros"

  • 输出:3

  • 解释: horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e')

  • 示例 2:

  • 输入:word1 = "intention", word2 = "execution"

  • 输出:5

  • 解释: intention -> inention (删除 't') inention -> enention (将 'i' 替换为 'e') enention -> exention (将 'n' 替换为 'x') exention -> exection (将 'n' 替换为 'c') exection -> execution (插入 'u')

提示:

  • 0 <= word1.length, word2.length <= 500
  • word1 和 word2 由小写英文字母组成

思路

#1. 确定dp数组(dp table)以及下标的含义

dp[i][j] 表示以下标i-1为结尾的字符串word1,和以下标j-1为结尾的字符串word2,最近编辑距离为dp[i][j]

#2. 确定递推公式

if (word1[i - 1] == word2[j - 1]) 那么说明不用任何编辑,即dp[i][j] = dp[i - 1][j - 1];

if (word1[i - 1] != word2[j - 1]),此时就需要编辑了:

  • 操作一:word1删除一个元素,那么就是以下标i - 2为结尾的word1 与 j-1为结尾的word2的最近编辑距离 再加上一个操作。

即 dp[i][j] = dp[i - 1][j] + 1;

  • 操作二:word2删除一个元素,那么就是以下标i - 1为结尾的word1 与 j-2为结尾的word2的最近编辑距离 再加上一个操作。

即 dp[i][j] = dp[i][j - 1] + 1;

word2添加一个元素,相当于word1删除一个元素,例如 word1 = "ad" ,word2 = "a"word1删除元素'd' 和 word2添加一个元素'd',变成word1="a", word2="ad"

操作三:替换元素,word1替换word1[i - 1],使其与word2[j - 1]相同,此时不用增删加元素。

可以回顾一下,if (word1[i - 1] == word2[j - 1])的时候我们的操作 是 dp[i][j] = dp[i - 1][j - 1] 对吧。

那么只需要一次替换的操作,就可以让 word1[i - 1] 和 word2[j - 1] 相同。

所以 dp[i][j] = dp[i - 1][j - 1] + 1;

综上,当 if (word1[i - 1] != word2[j - 1]) 时取最小的,即:dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;

递归公式代码如下:

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], dp[i - 1][j], dp[i][j - 1]}) + 1;
}

#3. dp数组如何初始化

再回顾一下dp[i][j]的定义:

dp[i][j] 表示以下标i-1为结尾的字符串word1,和以下标j-1为结尾的字符串word2,最近编辑距离为dp[i][j]

dp[i][0] :以下标i-1为结尾的字符串word1,和空字符串word2,最近编辑距离为dp[i][0]。

那么dp[i][0]就应该是i,对word1里的元素全部做删除操作,即:dp[i][0] = i; 同理dp[0][j] = j;

#4. 确定遍历顺序

从左到右从上到下去遍历。

class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));
        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 = 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];
                }
                else {
                    dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
                }
            }
        }
        return dp[word1.size()][word2.size()];
    }
};

  • 时间复杂度: O(n * m)
  • 空间复杂度: O(n * m)

647. 回文子串

力扣题目链接(opens new window)

给定一个字符串,你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被视作不同的子串。

示例 1:

  • 输入:"abc"
  • 输出:3
  • 解释:三个回文子串: "a", "b", "c"

示例 2:

  • 输入:"aaa"
  • 输出:6
  • 解释:6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

提示:输入的字符串长度不会超过 1000 。

思路

暴力解法

两层for循环,遍历区间起始位置和终止位置,然后还需要一层遍历判断这个区间是不是回文。所以时间复杂度:O(n^3)

动态规划

动规五部曲:

  1. 确定dp数组(dp table)以及下标的含义

布尔类型的dp[i][j]:表示区间范围[i,j] (注意是左闭右闭)的子串是否是回文子串,如果是dp[i][j]为true,否则为false。

  1. 确定递推公式

在确定递推公式时,就要分析如下几种情况。

整体上是两种,就是s[i]与s[j]相等,s[i]与s[j]不相等这两种。

当s[i]与s[j]不相等,那没啥好说的了,dp[i][j]一定是false。

当s[i]与s[j]相等时,这就复杂一些了,有如下三种情况

  • 情况一:下标i 与 j相同,同一个字符例如a,当然是回文子串
  • 情况二:下标i 与 j相差为1,例如aa,也是回文子串
  • 情况三:下标:i 与 j相差大于1的时候,例如cabac,此时s[i]与s[j]已经相同了,我们看i到j区间是不是回文子串就看aba是不是回文就可以了,那么aba的区间就是 i+1 与 j-1区间,这个区间是不是回文就看dp[i + 1][j - 1]是否为true。

以上三种情况分析完了,那么递归公式如下:

if (s[i] == s[j]) {
    if (j - i <= 1) { // 情况一 和 情况二
        result++;
        dp[i][j] = true;
    } else if (dp[i + 1][j - 1]) { // 情况三
        result++;
        dp[i][j] = true;
    }
}

result就是统计回文子串的数量。

注意这里我没有列出当s[i]与s[j]不相等的时候,因为在下面dp[i][j]初始化的时候,就初始为false。

  1. dp数组初始化为false。
  2. 确定遍历顺序

遍历顺序可有有点讲究了。

首先从递推公式中可以看出,情况三是根据dp[i + 1][j - 1]是否为true,在对dp[i][j]进行赋值true的。

dp[i + 1][j - 1] 在 dp[i][j]的左下角,如图:

647.回文子串

如果这矩阵是从上到下,从左到右遍历,那么会用到没有计算过的dp[i + 1][j - 1],也就是根据不确定是不是回文的区间[i+1,j-1],来判断了[i,j]是不是回文,那结果一定是不对的。

所以一定要从下到上,从左到右遍历,这样保证dp[i + 1][j - 1]都是经过计算的

注意因为dp[i][j]的定义,所以j一定是大于等于i的,那么在填充dp[i][j]的时候一定是只填充右上半部分

class Solution {
public:
    int countSubstrings(string s) {
        vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
        int result = 0;
        for (int i = s.size() - 1; i >= 0; i--) {
            for (int j = i; j < s.size(); j++) {
                if (s[i] == s[j] && (j - i <= 1 || dp[i + 1][j - 1])) {
                    result++;
                    dp[i][j] = true;
                }
            }
        }
        return result;
    }
};
  • 时间复杂度:O(n^2)
  • 空间复杂度:O(n^2)

#双指针法

动态规划的空间复杂度是偏高的,我们再看一下双指针法。

首先确定回文串,就是找中心然后向两边扩散看是不是对称的就可以了。

在遍历中心点的时候,要注意中心点有两种情况

一个元素可以作为中心点,两个元素也可以作为中心点。

那么有人同学问了,三个元素还可以做中心点呢。其实三个元素就可以由一个元素左右添加元素得到,四个元素则可以由两个元素左右添加元素得到。

所以我们在计算的时候,要注意一个元素为中心点和两个元素为中心点的情况。

这两种情况可以放在一起计算,但分别计算思路更清晰,我倾向于分别计算,代码如下:

class Solution {
public:
    int countSubstrings(string s) {
        int result = 0;
        for (int i = 0; i < s.size(); i++) {
            result += extend(s, i, i, s.size()); // 以i为中心
            result += extend(s, i, i + 1, s.size()); // 以i和i+1为中心
        }
        return result;
    }
    int extend(const string& s, int i, int j, int n) {
        int res = 0;
        while (i >= 0 && j < n && s[i] == s[j]) {
            i--;
            j++;
            res++;
        }
        return res;
    }
};
  • 时间复杂度:O(n^2)
  • 空间复杂度:O(1)

516.最长回文子序列

力扣题目链接(opens new window)

给定一个字符串 s ,找到其中最长的回文子序列,并返回该序列的长度。可以假设 s 的最大长度为 1000 。

示例 1: 输入: "bbbab" 输出: 4 一个可能的最长回文子序列为 "bbbb"。

示例 2: 输入:"cbbd" 输出: 2 一个可能的最长回文子序列为 "bb"。

提示:

  • 1 <= s.length <= 1000
  • s 只包含小写英文字母

思路

 动态规划:回文子串 (opens new window),求的是回文子串,而本题要求的是回文子序列。

回文子串是要连续的,回文子序列可不是连续的! 

动规五部曲分析如下:

  1. 确定dp数组(dp table)以及下标的含义

dp[i][j]:字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]

  1. 确定递推公式

如果s[i]与s[j]相同,那么dp[i][j] = dp[i + 1][j - 1] + 2;

如图: 

516.最长回文子序列

如果s[i]与s[j]不相同,说明s[i]和s[j]的同时加入 并不能增加[i,j]区间回文子序列的长度,那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。

加入s[j]的回文子序列长度为dp[i + 1][j]。

加入s[i]的回文子序列长度为dp[i][j - 1]。

那么dp[i][j]一定是取最大的,即:dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

516.最长回文子序列1

  1. dp数组初始化

首先要考虑当i 和j 相同的情况,从递推公式:dp[i][j] = dp[i + 1][j - 1] + 2; 可以看出 递推公式是计算不到 i 和j相同时候的情况。

所以需要手动初始化一下,当i与j相同,那么dp[i][j]一定是等于1的,即:一个字符的回文子序列长度就是1。

其他情况dp[i][j]初始为0就行,这样递推公式:dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); 中dp[i][j]才不会被初始值覆盖。

  1. 确定遍历顺序

从递归公式中,可以看出,dp[i][j] 依赖于 dp[i + 1][j - 1] ,dp[i + 1][j] 和 dp[i][j - 1],如图:

所以遍历i的时候一定要从下到上遍历,这样才能保证下一行的数据是经过计算的

j的话,可以正常从左向右遍历。

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
        for (int i = 0; i < s.size(); i++) dp[i][i] = 1;
        for (int i = s.size() - 1; i >= 0; i--) {
            for (int j = i + 1; j < s.size(); j++) {
                if (s[i] == s[j]) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][s.size() - 1];
    }
};
  • 时间复杂度: O(n^2)
  • 空间复杂度: O(n^2)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/722702.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

QT6不自动生成pro文件

安装了QT的新版本结果他不自动生成pro文件了导致下次打开很复杂 记得在创建时选择qmake&#xff0c;因为新版默认cmake

宝塔软件默认安装位置

自带的JDK /usr/local/btjdk/jdk8Tomcat 各个版本都在bttomcat这个文件夹下面&#xff0c;用版本区分。tomcat_bak8是备份文件 /usr/local/bttomcat/tomcat8nginx /www/server/nginxnginx配置文件存放目录 /www/server/panel/vhost/nginxredis /www/server/redismysql /…

财讯杂志财讯杂志社财讯编辑部2024年第6期目录查询

财税研究 “互联网税务”模式在企业税务管理中的应用 陈飞; 1-3 国有企业税务稽查的问题与对策研究 梁涵瑜; 4-6 税务师事务所执业质量内部控制优化路径及风险防范 万晓玲; 7-9《财讯》投稿&#xff1a;cnqikantg126.com 基于全过程的新能源电力投资企业税务筹…

宝塔面板使用技巧(pure-FTP)上传文件和文件夹默认权限644的修改

前言 科技在进步各种各样的开源软件和库让我们应接不暇&#xff0c;我估计现在所有做php开发的人员都知道宝塔面板&#xff0c;我就经常用&#xff0c;但是不知道大家出现过一个问题不就是在我们开发过程中需要实时的给服务器上传我们开发的文件那么就涉及到了宝塔自带的pure-F…

BC-Linux 8.6最小化安装的服务器启用GNOME图形化界面

本文记录了BC-Linux 8.6最小化安装的服务器如何启用GNOME图形化界面的过程。 一、服务器环境 1、系统版本 [rootlocalhost ~]# cat /etc/os-release NAME"BigCloud Enterprise Linux" VERSION"8.6 (Core)" ID"bclinux" ID_LIKE"rhel fe…

央国企财务专家的“专家课”——中国总会计师协会联合实在智能举办RPA专项培训

近日&#xff0c;中国总会计师协会正式举办了为期五天的「财务数字化思维与实用IT技能提升」专项培训&#xff0c;吸引了来自中铁十五局集团有限公司、中国航空工业规划设计院、中核核电运行管理有限公司、中国北方车辆有限公司、一汽物流有限公司等国企、事业单位及民营企业共…

eclipse宝刀未老

Theia 是一个高度可定制的、开源的、基于 Web 的集成开发环境&#xff08;IDE&#xff09;框架。它由 Eclipse Foundation 主导&#xff0c;旨在为云和本地环境提供现代化的、全功能的 IDE 解决方案。Theia 的核心目标是提供一个灵活的平台&#xff0c;开发者可以根据自己的需求…

【ARM】MDK自动备份源文件

【更多软件使用问题请点击亿道电子官方网站】 1、 文档目标 解决MDK在编写文档的时候需要找回上一版代码的问题。 2、 问题场景 目前大部分情况下对于源代码的管理都是使用的Git等第三方的代码管理平台。这样的第三方代码管理平台都是针对与代码的版本更新进行管理。对于本地…

帕金森患者宜居环境指南,温馨舒适助康复

&#x1f338;帕金森病&#xff0c;优质的居住环境能极大地提升患者的生活质量。今天&#xff0c;就为大家分享一下帕金森患者宜居环境的几个关键点&#xff0c;希望每位患者都能拥有一个温馨舒适的康复空间。 &#x1f6cb;️首先&#xff0c;布局要合理。对于帕金森患者来说&…

XMLXXE实体注入

XML&XXE实体注入 原理 XML被设计为传输和存储数据&#xff0c;XML文档结构包括XML声明、DTD文档类型定义&#xff08;可选&#xff09;、文档元素&#xff0c;其焦点是数据的内容&#xff0c;其把数据从HTML分离&#xff0c;是独立于软件和硬件的信息传输工具。等同于JSO…

【面试干货】Java方法重写的规则

【面试干货】Java方法重写的规则 1、Java方法重写的规则2、示例代码3、总结 &#x1f496;The Begin&#x1f496;点点关注&#xff0c;收藏不迷路&#x1f496; 在Java中&#xff0c;方法重写&#xff08;Overriding&#xff09;是面向对象编程中的一个核心概念&#xff0c;它…

具备智能灵敏度校准并可Pin to Pin替代TSM12的电容式触摸芯片GTX312L

电容式触摸芯片 - GTX312L是一款具有智能灵敏度校准功能的12通道电容式触摸芯片&#xff0c;采用I2C通信协议&#xff0c;对各种噪音和环境的变化可靠性有保障&#xff0c;低功率发动机可以增加产品的使用时间&#xff0c;内部控制寄存器可以使用I2C读写接口。 GTX312L具有内部…

记一次 .NET某机械臂上位系统 卡死分析

一&#xff1a;背景 1. 讲故事 前些天有位朋友找到我&#xff0c;说他们的程序会偶发性的卡死一段时间&#xff0c;然后又好了&#xff0c;让我帮忙看下怎么回事&#xff1f;窗体类的程序解决起来相对来说比较简单&#xff0c;让朋友用procdump自动抓一个卡死时的dump&#x…

windows anaconda 安装 Labelme

安装 # 创建环境 conda create -n labelme python3.6 #激活环境 conda activate labelme # 安装依赖 conda install pyqt conda install pillow # 安装labelme conda install labelme3.16.2 # 启动labelme labelme右键选择标注类型&#xff0c;从上到下为多边形&#xff08;常…

Git分支的状态存储——stash命令的详细用法

文章目录 6.6 Git的分支状态存储6.6.1 git stash命令6.6.2 Git存储的基本使用6.6.3 Git存储的其他用法6.6.4 Git存储与暂存区6.6.5 Git存储的原理 6.6 Git的分支状态存储 有时&#xff0c;当我们在项目的一部分上已经工作一段时间后&#xff0c;所有东西都进入了混乱的状态&am…

机器学习课程复习——朴素贝叶斯

1. 定义 是一种基于贝叶斯定理与特征条件独立假设的生成式分类方法。 2. 公式 原版公式 简化版公式 由于上述公式无法计算&#xff0c;引入条件独立假设 条件独立版公式 3. 贝叶斯分类器 由上述公式可得贝叶斯分类器 化简为 4. 参数估计 4.1. 极大似然估计 4.2. 学习与分…

电子竞赛5——作息时间控制器

一 . 题目要求 用单片机制作作息时间控制器&#xff1b;用四位数码管显示实时时钟&#xff08;时、分&#xff0c;24小时制、12小时制&#xff09;&#xff0c;有秒闪&#xff0c;小时十位有零消隐&#xff1b;可用数字键或、-键校时&#xff08;可快速、-&#xff09;被校位&…

离线安装zabbix-agent,自制yum源方式安装

1&#xff0c;机器准备 现在有2台机器 机器A&#xff0c;能上网&#xff0c;ip&#xff1a;192.168.10.131&#xff1b; 机器B&#xff0c;不能上网&#xff0c;ip&#xff1a;192.168.10.133。 我想在机器B上面安装zabbix-agent-5.0.42版本。 大致思路 在机器A上面制作好我…

Midjourney和Stable Diffusion哪个更适合商业应用?

midjourney的绘画&#xff0c;在撰写有效的prompt需要精确地定义你想要展现的画面&#xff0c;详细描述越准确&#xff0c;生成出的图片结果也会越吻合你的预期。为了提升你midjourney的写作prompt的技巧&#xff0c;可以通过模仿他人的成功案例&#xff0c;亲自尝试编写&#…

C++ 68 之 类模版作函数的参数

#include <iostream> // #include <cstring> #include <string> using namespace std;template<class T1, class T2> // 可以设置默认的类型值&#xff0c;后面在使用的时候&#xff0c;就不用再指定类型了 class Students08{ public:T1 m_name;T2 m_a…