算法沉淀——动态规划之回文串问题（上）（leetcode真题剖析）

在这里插入图片描述

算法沉淀——动态规划之回文串问题

  • 01.回文子串
  • 02.最长回文子串
  • 03.分割回文串 IV
  • 04.分割回文串 II
  • 05.最长回文子序列
  • 06.让字符串成为回文串的最少插入次数

01.回文子串

题目链接：https://leetcode.cn/problems/palindromic-substrings/

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

回文字符串 是正着读和倒过来读一样的字符串。

子字符串 是字符串中的由连续字符组成的一个序列。

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

示例 1：

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

示例 2：

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

提示：

  • 1 <= s.length <= 1000
  • s 由小写英文字母组成

思路

  1. 预处理回文信息： 创建一个 dp 表，其中 dp[i][j] 表示字符串 s 中子串 s[i:j+1] 是否是回文串。

  2. 状态转移方程： 对于回文串，分析两头的元素：

    • 如果 s[i] != s[j]，则不可能是回文串，dp[i][j] = 0；

    • 如果

      s[i] == s[j]

      ，则根据长度分三种情况讨论：

      • 如果长度为 1，即 i == j，则一定是回文串，dp[i][j] = true；
      • 如果长度为 2，即 i + 1 == j，则也一定是回文串，dp[i][j] = true；
      • 如果长度大于 2，则需要看 [i + 1, j - 1] 区间的子串是否回文，dp[i][j] = dp[i + 1][j - 1]。

  3. 初始化： 由于状态转移方程已经考虑了各种情况，无需额外初始化。

  4. 填表顺序： 根据状态转移方程，从下往上填写每一行。

  5. 返回值： 根据状态表达和题目要求，返回 dp 表中 true 的个数。

代码

class Solution {
public:int countSubstrings(string s) {int n=s.size();vector<vector<bool>> dp(n,vector<bool>(n));int sum=0;for(int i=n-1;i>=0;i--){for(int j=i;j<n;j++){if(s[i]==s[j]) dp[i][j]=i+1<j?dp[i+1][j-1]:true;if(dp[i][j]) sum++;}}return sum;}
};

02.最长回文子串

题目链接：https://leetcode.cn/problems/longest-palindromic-substring/

给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

提示：

  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母组成

思路

和上一题思路基本一致，但这里我们要返回字串，所以我们需要在原有算法上标记字串的开始位置和子串的长度。

代码

class Solution {
public:string longestPalindrome(string s) {int n=s.size();vector<vector<bool>> dp(n,vector<bool>(n));int len=1,begin=0;for(int i=n-1;i>=0;--i){for(int j=i;j<n;++j){if(s[i]==s[j]) dp[i][j]=i+1<j?dp[i+1][j-1]:true;if(dp[i][j]&&j-i+1>len) len=j-i+1,begin=i;}}return s.substr(begin,len);}
};

03.分割回文串 IV

题目链接：https://leetcode.cn/problems/palindrome-partitioning-iv/

给你一个字符串 s ，如果可以将它分割成三个 非空 回文子字符串，那么返回 true ，否则返回 false 。

当一个字符串正着读和反着读是一模一样的，就称其为 回文字符串 。

示例 1：

输入：s = "abcbdd"
输出：true
解释："abcbdd" = "a" + "bcb" + "dd"，三个子字符串都是回文的。

示例 2：

输入：s = "bcbddxy"
输出：false
解释：s 没办法被分割成 3 个回文子字符串。

提示：

  • 3 <= s.length <= 2000
  • s 只包含小写英文字母。

思路

其实这里我们可以依照第一题的解法将所有的子串都进行统计，再遍历计算每个分割位置组成的3个子串是否都符合回文子串即可。

代码

class Solution {
public:bool checkPartitioning(string s) {int n=s.size();vector<vector<bool>> dp(n,vector<bool>(n));for(int i=n-1;i>=0;--i)for(int j=i;j<n;j++)if(s[i]==s[j]) dp[i][j]=i+1<j?dp[i+1][j-1]:true;for(int i=1;i<n-1;i++)for(int j=i;j<n-1;++j)if(dp[0][i-1]&&dp[i][j]&&dp[j+1][n-1]) return true;return false;}
};

04.分割回文串 II

题目链接：https://leetcode.cn/problems/palindrome-partitioning-ii/

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。

返回符合要求的 最少分割次数 。

示例 1：

输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

示例 2：

输入：s = "a"
输出：0

示例 3：

输入：s = "ab"
输出：1

提示：

  • 1 <= s.length <= 2000
  • s 仅由小写英文字母组成

思路

  1. 状态表达： 以 i 位置为结尾，定义状态表达 dp[i] 表示字符串 s 中 [0, i] 区间上的字符串，最少分割的次数。

  2. 状态转移方程： 通常考虑最后一个位置的信息。设 0 <= j <= i，那么可以根据 [j, i] 位置上的子串是否是回文串分成以下两类：

    • 如果 [j, i] 位置上的子串能够构成一个回文串，那么 dp[i] 就等于 [0, j - 1] 区间上最少回文串的个数 + 1，即 dp[i] = dp[j - 1] + 1；
    • 如果 [j, i] 位置上的子串不能构成一个回文串，此时 j 位置就不用考虑。

    由于求的是最小值，因此需要循环遍历 j 的取值，取最小值。

  3. 优化： 在状态转移方程中，需要快速判断字符串中的子串是否回文。因此，可以先处理一个 dp 表，其中保存所有子串是否回文的信息。

  4. 初始化： 在循环遍历 j 之前，处理 j == 0 的情况。此时，表示的区间是 [0, i]。如果 [0, i] 区间上的字符串已经是回文串了，最小的回文串就是 1，j 往后的值就不用遍历了。为防止在求 min 操作时，0 干扰结果，将表中的值初始化为「无穷大」。

  5. 填表顺序： 从左往右填写。

  6. 返回值： 根据状态表达，返回 dp[n - 1]。

代码

class Solution {
public:int minCut(string s) {int n=s.size();vector<vector<bool>> isp(n,vector<bool>(n));for(int i=n-1;i>=0;--i)for(int j=i;j<n;j++)if(s[i]==s[j]) isp[i][j]=i+1<j?isp[i+1][j-1]:true;vector<int> dp(n,INT_MAX);for(int i=0;i<n;++i){if(isp[0][i]) dp[i]=0;else{for(int j=1;j<=i;j++)if(isp[j][i]) dp[i]=min(dp[i],dp[j-1]+1);}}return dp[n-1];}
};

05.最长回文子序列

题目链接：https://leetcode.cn/problems/longest-palindromic-subsequence/

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：

输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。

示例 2：

输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。

提示：

  • 1 <= s.length <= 1000
  • s 仅由小写英文字母组成

思路

  1. 状态表达： 以 i 位置为结尾，定义状态表达 dp[i][j] 表示字符串 s 中 [i, j] 区间内的所有子序列中，最长的回文子序列的长度。

  2. 状态转移方程： 回文子序列和回文子串的分析方式一般都是选择这段区域的「左右端点」的字符情况来分析。因为如果一个序列是回文串的话，「去掉首尾两个元素之后依旧是回文串」，「首尾加上两个相同的元素之后也依旧是回文串」。根据首尾元素的不同，分为以下两种情况：

    • 当 s[i] == s[j] 时，[i, j] 区间上的最长回文子序列，应该是 [i + 1, j - 1] 区间内的那个最长回文子序列首尾填上 s[i] 和 s[j]，此时 dp[i][j] = dp[i + 1][j - 1] + 2。
    • 当 s[i] != s[j] 时，这两个元素就不能同时添加在一个回文串的左右，那么就应该让 s[i] 单独加在一个序列的左边，或者让 s[j] 单独放在一个序列的右边，看看这两种情况下的最大值：
      • 单独加入 s[i] 后的区间在 [i, j - 1]，此时最长的回文序列的长度就是 dp[i][j - 1]；
      • 单独加入 s[j] 后的区间在 [i + 1, j]，此时最长的回文序列的长度就是 dp[i + 1][j]；

    取两者的最大值，于是 dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])。

  3. 初始化： 需要处理两种边界情况：

    • 当 i == j 时，区间内只有一个字符，此时 dp[i][j] = 1；
    • 当 i + 1 == j 时，区间内有两个字符，如果这两个字符相同，dp[i][j] = 2，否则 dp[i][j] = 0。

    在填表的时候，可以同步处理第一种边界情况，对于第二种边界情况，dp[i + 1][j - 1] 的值为 0，不会影响最终的结果，因此可以不用考虑。

  4. 填表顺序： 根据「状态转移」，dp[i + 1] 表示下一行的位置，dp[j - 1] 表示前一列的位置。因此填表顺序应该是「从下往上填写每一行」，「每一行从左往右」。

  5. 返回值： 根据「状态表达」，返回 [0, n -1] 区域上的最长回文序列的长度，因此需要返回 dp[0][n - 1]。

代码

class Solution {
public:int longestPalindromeSubseq(string s) {int n=s.size();vector<vector<int>> dp(n,vector<int>(n));for(int i=n-1;i>=0;i--){dp[i][i]=1;for(int j=i+1;j<n;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][n-1];}
};

06.让字符串成为回文串的最少插入次数

题目链接：https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/

给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。

请你返回让 s 成为回文串的 最少操作次数 。

「回文串」是正读和反读都相同的字符串。

示例 1：

输入：s = "zzazz"
输出：0
解释：字符串 "zzazz" 已经是回文串了，所以不需要做任何插入操作。

示例 2：

输入：s = "mbadm"
输出：2
解释：字符串可变为 "mbdadbm" 或者 "mdbabdm" 。

示例 3：

输入：s = "leetcode"
输出：5
解释：插入 5 个字符后字符串变为 "leetcodocteel" 。

提示：

  • 1 <= s.length <= 500
  • s 中所有字符都是小写字母。

思路

  1. 状态表达： 以 i 位置为结尾，定义状态表达 dp[i][j] 表示字符串 s 中 [i, j] 区域成为回文子串的最少插入次数。
  2. 状态转移方程： 回文子序列和回文子串的分析方式一般都是选择这段区域的「左右端点」的字符情况来分析。因为如果一个序列是回文串的话，「去掉首尾两个元素之后依旧是回文串」，「首尾加上两个相同的元素之后也依旧是回文串」。根据首尾元素的不同，可以分为以下两种情况：
    • 当 s[i] == s[j] 时，[i, j] 区间内成为回文子串的最少插入次数，取决于 [i + 1, j - 1] 区间内成为回文子串的最少插入次数。若 i >= j - 1 或 i == j - 1 （ [i + 1, j - 1] 不构成合法区间），此时只有 1 ~ 2 个相同的字符， [i, j] 区间一定是回文子串，成为回文子串的最少插入次数是 0。此时 dp[i][j] = i >= j - 1 ? 0 : dp[i + 1][j - 1]。
    • 当 s[i] != s[j] 时，需要在区间的最右边或最左边插入一个字符，取决于 [i + 1, j] 或 [i, j + 1] 区间内成为回文子串的最少插入次数。此时 dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1。
  3. 初始化： 根据「状态转移方程」，没有不能递推表达的值，无需初始化。
  4. 填表顺序： 根据「状态转移」，dp[i + 1] 表示下一行的位置，dp[j - 1] 表示前一列的位置。因此填表顺序应该是「从下往上填写每一行」，「每一行从左往右」。
  5. 返回值： 根据「状态表达」，返回 [0, n - 1] 区域上成为回文子串的最少插入次数，因此需要返回 dp[0][n - 1]。

代码

class Solution {
public:int minInsertions(string s) {int n=s.size();vector<vector<int>> dp(n,vector<int>(n));for(int i=n-1;i>=0;i--){for(int j=i+1;j<n;j++){if(s[i]==s[j]) dp[i][j]=dp[i+1][j-1];else dp[i][j]=min(dp[i+1][j],dp[i][j-1])+1;}}return dp[0][n-1];}
};

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

如若内容造成侵权/违法违规/事实不符，请联系瞎胡闹网进行投诉反馈，一经查实，立即删除！

相关文章

Android 架构MVI、MVVM、MVC、MVP

Android 架构MVI、MVVM、MVC、MVP

目录 一、MVC&#xff08;Model-View-Controller&#xff09; 二、 MVP&#xff08;Model-View-Presenter&#xff09; 三. MVVM&#xff08;Model-View-ViewModel&#xff09; 四. MVI&#xff08;Model-View-Intent&#xff09; 五.MVI简单实现 先简单了解一下MVC、MVP和…
阅读更多...
LabVIEW磁阻自动优化测量系统

LabVIEW磁阻自动优化测量系统

LabVIEW磁阻自动优化测量系统 介绍了一种基于LabVIEW开发的磁阻自动优化测量系统&#xff0c;通过自动优化测试分辨率和高度模块化设计&#xff0c;大幅提升磁阻测试的效率和准确性。系统采用功率电源、电磁铁、高分辨率特斯拉计、步进电机转动器、精密电流源与精准电压表等硬…
阅读更多...
ruoyi框架学习

ruoyi框架学习

RBAC模型 数据字典 拦截器 token没有&#xff0c;submit&#xff0c;request.js中&#xff0c;前端前置拦截器&#xff0c;响应拦截器 后台 注解
阅读更多...
Word | 论文使用 Springer LNICST 工具包进行格式化

Word | 论文使用 Springer LNICST 工具包进行格式化

目录 Step1&#xff1a;下载 Springer LNICST 工具包 Step2&#xff1a;导入宏文件 Step3&#xff1a;处理导入失败&#xff08;大概意思是这个宏不安全&#xff09; Step4&#xff1a;导入成功并使用 Step1&#xff1a;下载 Springer LNICST 工具包 会议官网的 SUBMISSIO…
阅读更多...
当你使用ChatGPT时，选择合适的提示（prompt）是引导对话方向的关键

当你使用ChatGPT时，选择合适的提示（prompt）是引导对话方向的关键

马斯克曾说&#xff0c;人生中最重要的事情&#xff0c;就是提出真正的好问题。 因此&#xff0c;我要开始接触某个新领域&#xff0c;并且开始要自主学习的时候&#xff0c;我首先要问自己这个问题&#xff1a; 我为什么要学这个&#xff0c;学这个的目的是为了创造什么&#…
阅读更多...
project.config.json 文件内容错误] project.config.json: libVersion 字段需为 string, string

project.config.json 文件内容错误] project.config.json: libVersion 字段需为 string, string

家人们&#xff0c;遇到了一个新的报错 于是从网上找了各种方法&#xff0c;有说把开发者工具关闭重启的&#xff0c;有说开发者工具下载重新下载的&#xff0c;有说开发者工具路径安装得在C盘的&#xff0c;均没有效果 解决方法&#xff1a; 1、运行项目&#xff0c;在开发者…
阅读更多...
软件需求分析报告（直接套用）

软件需求分析报告（直接套用）

技术要求 1.1接口要求 1.2可靠性&#xff0c;稳定性&#xff0c;安全性&#xff0c;先进性&#xff0c;拓展性&#xff0c;性能&#xff0c;响应。 2.系统安全需求 2.1物理设计安全 2.2系统安全设计 2.3网络安全设计 2.4应用安全设计 2.5用户安全管理 全套资料过去进主页。
阅读更多...
Vue3之属性传值的四种情况

Vue3之属性传值的四种情况

文章目录 Vue3之属性传值的四种情况一、引言二、父组件向子组件传值三、子组件向父组件传值四、祖先组件向后代组件传值五、兄弟组件之间传值 Vue3之属性传值的四种情况 一、引言 在vue3中&#xff0c;组件与组件之间是可以传递属性的&#xff0c;包括三种类型&#xff1a; …
阅读更多...
爱旅行平台的设计与实现

爱旅行平台的设计与实现

爱旅行平台的设计与实现 获取源码——》公主号&#xff1a;计算机专业毕设大全
阅读更多...
Oracle中序列

Oracle中序列

1. Sequence 定义 在Oracle中可以用SEQUENCE生成自增字段。Sequence序列是Oracle中用于生成数字序列的对象&#xff0c;可以创建一个唯一的数字作为主键。 2. 为什么要用 Sequence 你可能有疑问为什么要使用序列&#xff1f; 不能使用一个存储主键的表并每次递增吗&#xf…
阅读更多...
java 反射机制 (一)

java 反射机制 (一)

java反射机制&#xff1a; 即通过外部文件配置&#xff0c;不修改文件源码的情况下&#xff0c;来控制程序&#xff0c;也符合设计模式的OCP原则&#xff08;开闭原则&#xff1a;不修改源码&#xff0c;扩容原则&#xff09; Java Reflection 1.反射机制允许程序在执行期间…
阅读更多...
Spring中的事务和事务的传播机制

Spring中的事务和事务的传播机制

事务是一组操作的集合&#xff0c;不可以被分割。事务会把所有的操作作为一个整体&#xff0c;这组操作要么全部成功&#xff0c;要么全部失败。 事务有三种操作&#xff1a; 开启事务&#xff1b;提交事务&#xff1b;回滚事务。 如果代码的执行逻辑是这样&#xff1a; 开…
阅读更多...
dolphinscheduler海豚调度（三）SQL任务

dolphinscheduler海豚调度（三）SQL任务

在之前的博文中&#xff0c;我们已经介绍了DolphinScheduler海豚调度的基本概念和模块&#xff0c;安装部署和元数据切换&#xff0c;以及Shell任务的实践。今天&#xff0c;让我们来深入探讨DolphinScheduler中另一种常见的任务类型&#xff1a;SQL任务。 SQL任务是DolphinSc…
阅读更多...
弹窗内容由后端返回，如何让点击按钮的事件交由前端控制?

弹窗内容由后端返回，如何让点击按钮的事件交由前端控制?

一、场景 背景&#xff1a;因为系统里经常有新活动或者公告需要通知所有用户&#xff0c;希望前端维护的这个弹窗里的内容可以由后端接口返回。这样就不需要每次上新活动的时候&#xff0c;前端项目都发版了。因此&#xff0c;前端维护了这个弹窗和它的关闭事件&#xff0c;至…
阅读更多...
人工智能之Tensorflow常用API

人工智能之Tensorflow常用API

TensorFlow的计算表现为数据流图&#xff0c;所以tf.Graph类中包含一系列表示计算的操作对象(tf.Operation)&#xff0c;以及在操作之间流动的数据–张量对象(tf.Tensor)。 Graph tf.Graph类包含图相关的API操作&#xff0c;可以在jupyter notebook导入tensorflow之后执行hel…
阅读更多...
前端Vue项目无法启动服务，提示无 ‘dev‘ npm的脚本问题解决

前端Vue项目无法启动服务，提示无 ‘dev‘ npm的脚本问题解决

目录 一、问题详情 二、问题解决 一、问题详情 上周还能运行的项目&#xff0c;今天突然无法执行了&#xff0c;连最基本的启动按钮也没有了&#xff0c;所有的项目本地都突然跑不起来了&#xff0c;附上截图。 二、问题解决 后来排查的根本原因有点奇葩&#xff0c;是因为…
阅读更多...
【踏雪无痕的痕四】——0到底是有还是没有？

【踏雪无痕的痕四】——0到底是有还是没有？

目录 一、背景介绍三、过程1.0的历史发展&#xff1f;2.如何将0讲给一个刚上一年级的孩子&#xff1f;3.0的边界和意义&#xff1f;4.那四年&#xff0c;到底在培养什么&#xff1f;和0有什么关系&#xff1f; 四、总结 一、背景介绍 最近在看一年级数学&#xff0c;其中介绍到…
阅读更多...
javaWeb个人学习02

javaWeb个人学习02

会话技术 会话: 用户打开浏览器,访问web服务器的资源,会话建立,直到有一方断开连接,会话结束.在一次会话中包含多次请求和响应 会话跟踪: 一种维护浏览器状态的方法,服务器需要识别多次请求是否来自于同一个浏览器,以便在同一次会话的多次请求之间共享数据 会话跟踪方案: …
阅读更多...
艺术作品展示图片介绍PR相册视频模板

艺术作品展示图片介绍PR相册视频模板

高级感艺术风格摄影、绘画作品展示文字介绍PR图片相册照片视频模板mogrt下载。 Premiere Pro 2023及以上版本&#xff0c;不需要插件&#xff0c;高清&#xff08;19201080&#xff09;分辨率/30fps&#xff0c;易于定制&#xff0c;持续时间01:00秒&#xff0c;包含PDF帮助文件…
阅读更多...
猜猜心里数字(个人学习笔记黑马学习)

猜猜心里数字(个人学习笔记黑马学习)

1.定义一个变量&#xff0c;数字类型&#xff0c;内容随意 2.基于input语句输入猜想的数字&#xff0c;通过if和多次elif的组合&#xff0c;判断猜想数字是否和心里数字一致 num5if int(input("请输入第一次猜想的数字&#xff1a;"))5:print("猜对了&#xff0…
阅读更多...
最新文章

Copyright @ 2022~2023