leetCode 5. 最长回文子串 动态规划 + 优化空间 / 中心扩展法 + 双指针

5. 最长回文子串 - 力扣(LeetC5. 最长回文子串 - 力扣(LeetCode)5. 最长回文子串 - 力扣(LeetC

给你一个字符串 s,找到 s 中最长的回文子串。如果字符串的反序与原始字符串相同,则该字符串称为回文字符串


示例 1:

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

示例 2:

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

一、中心扩展法 + 双指针​​​​​​​

我的往期文章有详细介绍​​​​​​​中心扩展法 + 双指针​​​​​​​,大家感兴趣可以看一下:​​​​​​​leetCode 647.回文子串 动态规划 + 优化空间 / 中心扩展法 + 双指针-CSDN博客icon-default.png?t=N7T8https://blog.csdn.net/weixin_41987016/article/details/133883091?spm=1001.2014.3001.5501

现在我们将用这个方法来解决本文中的此题:5. 最长回文子串 - 力扣(LeetCode)

class Solution {
public:vector<int> extend(string& s,int i,int j,int n) {while(i>=0 && j<n && s[i] == s[j]) {i--;j++;}return {i+1,j-1};}// 返回以 i, j 为中心的最长回文子串的左右边界string longestPalindrome(string s) {int n = s.size();vector<int> res{0,0};for(int i=0;i<n;i++) {vector<int> sub1 = extend(s,i,i,n);vector<int> sub2 = extend(s,i,i+1,n);if (res[1] - res[0] < sub1[1] - sub1[0]) res = sub1;if (res[1] - res[0] < sub2[1] - sub2[0]) res = sub2;}return s.substr(res[0], res[1] + 1 - res[0]);}
};
  • 时间复杂度:O(n^2)
  • 空间复杂度:O(1)

 二、动态规划(详细可以看我的往期文章:leetCode 647.回文子串

左边图是dp数组初始化,在填dp数组只会对右上三角进行数据更新,所以右边的图我就不画左下三角的0了。从图中,可得知有9true,即有9回文子串。还可以得知另一个信息,那就是回文子串有:"a","b","d","d","b","a","dd","bddb","abddba"

注:"dd"是回文子串的信息记录在(2,3)这个坐标,"bddb"是回文子串的信息记录在(1,4)这个坐标,"abddba"是回文子串的信息记录在(0,5)这个坐标,若为true,则该子串为回文。

(2,3),(1,4),(0,5)在左对角线上,所以观察的时候可以瞄准这条线上的坐标,分析信息

注:要明确和清晰dp[i][j] 表示区间范围[i,j]的子串是否为回文子串

这样就可以知道一个回文子串的起始和末尾,将其返回, 然后选取出最长回文子串

1.动态规划 二维dp 

class Solution {
public:// 动态规划 二维dp string longestPalindrome(string s) {vector<vector<bool>> dp(s.size(),vector<bool>(s.size(),false));vector<int> res{0,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])) {dp[i][j] = true;if (res[1] - res[0] < j - i) res = {i,j};}}}return s.substr(res[0], res[1] + 1 - res[0]);}
};
  • 时间复杂度:O(n^2)
  • 空间复杂度:O(n^2)

2.动态规划 二维dp + 优化空间

class Solution {
public: // 动态规划 二维dp 优化空间string longestPalindrome(string s) {vector<vector<bool>> dp(2,vector<bool>(s.size(),false));vector<int> res{0,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)%2][j-1])) {dp[i%2][j] = true;if (res[1] - res[0] < j - i) res = {i,j};}else {dp[i%2][j] = false;}}}return s.substr(res[0], res[1] + 1 - res[0]);}
};
  • 时间复杂度:O(n^2)
  • 空间复杂度:O(1)

 3.动态规划 一维dp + 优化空间

class Solution {
public:  // 动态规划 一维dp string longestPalindrome(string s) {vector<bool> dp(s.size(),false);vector<int> res{0,0};for(int i=s.size()-1;i>=0;i--) {bool pre = false;for(int j=i;j < s.size();j++) {bool tmp = dp[j];if(s[i] == s[j] && (j-i<=1 || pre)) {dp[j] = true;if (res[1] - res[0] < j - i) res = {i,j};}else {dp[j] = false;}pre = tmp;}}return s.substr(res[0], res[1] + 1 - res[0]);}
};
  • 时间复杂度:O(n^2)
  • 空间复杂度:O(1)

参考和推荐文章:

647. 回文子串 - 力扣(LeetCode)icon-default.png?t=N7T8https://leetcode.cn/problems/palindromic-substrings/solutions/1530868/by-lfool-2mvg/

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

数据结构----算法--排序算法

数据结构----算法–排序算法 一.冒泡排序&#xff08;BubbleSort&#xff09; 1.冒泡排序的核心思想 相邻两个元素进行大小比较&#xff0c;如果前一个比后一个大&#xff0c;就交换 注意&#xff1a; 在冒泡排序的过程中&#xff0c;促进了大的数往后去&#xff0c;小的数…

Spring事务和事务的传播机制(JavaEE进阶系列7)

目录 前言&#xff1a; 1.为什么需要事务 2.Spring中事务的实现 2.1编程式事务 2.2声明式事务 2.3Transactional的作用范围 2.4Transactional参数说明 2.5Transactional的注意事项 2.6Transactional工作原理 3.事务隔离级别 3.1事务特性的回顾 3.2Spring中设置事务…

区,段,碎片区与表空间结构

区&#xff0c;段&#xff0c;碎片区与表空间结构 结构图 另外在数据库中&#xff0c;还存在着区&#xff08;Extent&#xff09;&#xff0c;段&#xff08;Segment&#xff09;和表空间&#xff08;Tablespace&#xff09;的概念。行&#xff0c;页&#xff0c;区&#xff…

03_51单片机点亮LED灯

51单片机是一种非常常见的单片机型号&#xff0c;广泛应用于各种嵌入式系统和电子设备中。LED灯是一种常见的输出设备&#xff0c;用于显示信息或指示状态。下面是关于51单片机控制LED灯的介绍&#xff1a; 1. 连接LED灯&#xff1a;将LED的正极连接到51单片机的一个I/O引脚&a…

【LeetCode】33. 搜索旋转排序数组

1 问题 整数数组 nums 按升序排列&#xff0c;数组中的值 互不相同 。 在传递给函数之前&#xff0c;nums 在预先未知的某个下标 k&#xff08;0 < k < nums.length&#xff09;上进行了 旋转&#xff0c;使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nums…

【Linux】Ubuntu美化bash【教程】

【Linux】Ubuntu美化bash【教程】 文章目录 【Linux】Ubuntu美化bash【教程】1. 查看当前环境中是否有bash2. 安装Synth-Shell3. 配置Synth-Shell4. 取消greeterReference 1. 查看当前环境中是否有bash 查看当前使用的bash echo $SHELL如下所示 sjhsjhR9000X:~$ echo $SHELL…

在 Android 上恢复已删除音乐的 5 种简单方法

人们经常将重要的音乐文件保存在智能手机上&#xff0c;以方便随时随地收听自己喜欢的曲目。但是&#xff0c;如果这些珍贵的音乐文件因软件故障或硬件故障而被意外删除或丢失怎么办&#xff1f;这将是许多音乐爱好者的噩梦&#xff01; 如果您也是这些人中的一员&#xff0c;…

Linux shell编程学习笔记13:文件测试运算

Linux Shell 脚本编程和其他编程语言一样&#xff0c;支持算数、关系、布尔、逻辑、字符串、文件测试等多种运算。前面几节我们依次研究了 Linux shell编程 中的 字符串运算、算术运算、关系运算、布尔运算 和 逻辑运算&#xff0c;今天我们来研究 Linux shell编程中的文件测…

【设计模式-1】UML和设计原则

说明&#xff1a;设计模式&#xff08;Design Pattern&#xff09;对于软件开发&#xff0c;简单来说&#xff0c;就是软件开发的套路&#xff0c;固定模板。在学习设计模式之前&#xff0c;需要首先学习UML&#xff08;Unified Modeling Language&#xff0c;统一建模语言&…

(Python) Python中三种时间格式的转换方法

1. 时间元组 1.1. 时间元组和时间戳的互相转化 import time,datetime # 获取当前时间的时间元组 t time.localtime() print(t) # 时间元组转时间戳 timestamp time.mktime(t) print(timestamp) # time.struct_time(tm_year2019, tm_mon10, tm_mday23, tm_hour23, tm_min15,…

漏洞复现--安恒明御安全网关文件上传

免责声明&#xff1a; 文章中涉及的漏洞均已修复&#xff0c;敏感信息均已做打码处理&#xff0c;文章仅做经验分享用途&#xff0c;切勿当真&#xff0c;未授权的攻击属于非法行为&#xff01;文章中敏感信息均已做多层打马处理。传播、利用本文章所提供的信息而造成的任何直…

web 安全总结

1、web安全总结 1.1 web安全简介 1.1.1 http协议 http 协议是超文本传输协议-明文传输 https 协议是http协议的基础上进行升级&#xff0c;是数据在传输过程中进行加密 1.1.2 http请求 http请求分为&#xff1a;请求方法、请求头、请求体 GET、PUT、POST、OPTIONS、move、…

【Unity HDRP渲染管线下的WorleyUtilities文件,“Hash”函数】

Unity HDRP内置文件WorleyUtilities WorleyUtilities文件路径如下:文件代码如下然后转译到ShaderLab中:存档:WorleyUtilities文件路径如下: D:…\Library\PackageCache\com.unity.render-pipelines.high-definition@14.0.8\Runtime\Lighting\VolumetricClouds\WorleyUtili…

Ubuntu - 查看 IP 地址

要查看 Ubuntu 操作系统中的 IP 地址&#xff0c;可以使用 ip 命令或者 ifconfig 命令。以下是使用这两个命令的示例&#xff1a; 使用 ip 命令&#xff1a; 打开终端。 输入以下命令&#xff1a; ip a 这将显示网络接口信息&#xff0c;包括 IP 地址。通常&#xff0c;IP…

安科瑞预付费电能管理系统在学生公寓的应用与分析

安科瑞 崔丽洁 摘要&#xff1a;论文设计了适用于学生公寓的自助式预付费控电控水管理系统&#xff0c;采用多种智能功能&#xff0c;可以监测和显示漏电现象&#xff0c;通过短路、跳线、零线接地等方式防范和记录用户的偷电行为&#xff0c;通过报警和拉闸防止事故的发生。预…

嵌入式实时操作系统的设计与开发(调度策略学习)

将调度分为两层&#xff0c;上层为策略&#xff0c;下层为机制&#xff0c;并且采用策略与机制分离的设计原则&#xff0c;可以方便灵活地扩展调度策略&#xff0c;而不改变底层的调度机制。 调度策略就是如何确定线程的CPU、优先级prio等参数&#xff0c;线程是按照FIFO&…

掌控安全Update.jsp SQL注入

0x01 漏洞介绍 亿赛通电子文档安全管理系统是国内最早基于文件过滤驱动技术的文档加解密产品之一&#xff0c;保护范围涵盖终端电脑&#xff08;Windows、Mac、Linux系统平台&#xff09;、智能终端&#xff08;Android、IOS&#xff09;及各类应用系统&#xff08;OA、知识管理…

metaRTC7集成lvgl ui demo编译指南

概要 开源轻量级嵌入式图形库lvgl:Light and Versatile Graphics Library&#xff0c;最低只需8kb内存&#xff0c;可为任何 MCU、MPU 和显示类型创建漂亮的 UI。 metaRTC新增lvgl demo&#xff0c;可在linux下编译运行。 源码下载 https://github.com/metartc/metaRTC/rel…

小程序首页搭建

小程序首页搭建 1. Flex布局是什么&#xff1f;2. 容器的属性2.1 flex-direction属性2.2 flex-wrap属性2.3 flex-flow属性2.4 justify-content属性2.5 align-items属性2.6 align-content属性 二.首页布局搭建二.1moke模拟数据实现轮播图4.信息搭建 Flex弹性布局 1. Flex布局是…

Docker基础操作命令演示

Docker中的常见命令&#xff0c;可以参考官方文档&#xff1a;https://docs.docker.com/engine/reference/commandline/cli/ 1、常见命令介绍 其中&#xff0c;比较常见的命令有&#xff1a; 命令说明文档地址docker pull拉取镜像docker pulldocker push推送镜像到DockerReg…