LeetCode-5. 最长回文子串【字符串 动态规划】

LeetCode-5. 最长回文子串【字符串 动态规划】

  • 题目描述:
  • 解题思路一:动态规划五部曲
  • 解题思路二:动态规划[版本二]
  • 解题思路三:0

题目描述:

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

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

示例 1:

输入:s = “babad”
输出:“bab”
解释:“aba” 同样是符合题意的答案。
示例 2:

输入:s = “cbbd”
输出:“bb”

提示:

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

解题思路一:动态规划五部曲

  1. 定义dp[i][j]
    dp[i][j] 表示 s[i…j] 是否是回文串

  2. 推导公式
    当长度大于1,且s[i] == s[j]的时候才会更新dp数组
    那么就是L的长度为2或者3(j - i < 3)并且 s[i] == s[j]可以直接确定dp[i][j] = 1
    其他的就是状态转移方程:

dp[i][j] = dp[i+1][j-1]
  1. 初始化
dp = [[0] * n for _ in range(n)]
# dp[i][j] 表示 s[i..j] 是否是回文串
for i in range(n): # 长度为1必是回文串dp[i][i] = 1
  1. 遍历顺序
    先遍历字符串长度,后遍历左边界
for L in range(2, n+1):# 枚举左边界,左边界的上限设置可以宽松一些for i in range(n):
  1. 举例:
    在这里插入图片描述
class Solution:def longestPalindrome(self, s: str) -> str:n = len(s)if n < 2: return smax_len, begin = 1,0dp = [[0] * n for _ in range(n)]# dp[i][j] 表示 s[i..j] 是否是回文串for i in range(n): # 长度为1必是回文串dp[i][i] = 1# 先枚举子串长度for L in range(2, n+1):# 枚举左边界,左边界的上限设置可以宽松一些for i in range(n):j = L + i - 1 # # 由 L 和 i 可以确定右边界if j >= n: break # 如果右边界越界,就可以退出当前循环if s[i] == s[j]:if j - i < 3:dp[i][j] = 1else:dp[i][j] = dp[i+1][j-1]if dp[i][j] and L > max_len: # 只要 dp[i][L] == true 成立,就表示子串 s[i..L] 是回文,此时记录回文长度和起始位置max_len = Lbegin = ireturn s[begin: begin + max_len]

时间复杂度:O(n2)
空间复杂度:O(n2)

解题思路二:动态规划[版本二]

class Solution:def longestPalindrome(self, s: str) -> str:n = len(s)dp = [[0] * n for _ in range(n)]begin, max_len = 0, 1for i in range(n):dp[i][i] = 1for L in range(2, n+1):for i in range(n):j = L + i - 1if j >= n:breakif s[i] == s[j]:if j - i < 3:dp[i][j] = 1else:dp[i][j] = dp[i+1][j-1]if dp[i][j] and L > max_len:begin = imax_len = Lreturn s[begin: begin + max_len]

时间复杂度:O(n2)
空间复杂度:O(n2)

解题思路三:0


时间复杂度:O(n)
空间复杂度:O(n)

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

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

相关文章

【MYSQL】索引机制概述

由于MySQL是作为存储层部署在业务系统的最后端&#xff0c;所有的业务数据最终都要入库落盘&#xff0c;但随着一个项目在线上运行的时间越来越久&#xff0c;数据库中的数据量自然会越来越多&#xff0c;而数据体积出现增长后&#xff0c;当需要从表查询一些数据时&#xff0c…

网络安全入门教程(非常详细)从零基础入门到精通

网络安全是一个庞大而不断发展的领域&#xff0c;它包含多个专业领域&#xff0c;如网络防御、网络攻击、数据加密等。介绍网络安全的基本概念、技术和工具&#xff0c;逐步深入&#xff0c;帮助您成为一名合格的网络安全从业人员。 一、网络安全基础知识 1.计算机基础知识 …

蓝桥杯省赛冲刺(3)广度优先搜索

广度优先搜索&#xff08;Breadth-First Search, BFS&#xff09;是一种在图或树等非线性数据结构中遍历节点的算法&#xff0c;它从起始节点开始&#xff0c;按层级逐步向外扩展&#xff0c;即先访问离起始节点最近的节点&#xff0c;再访问这些节点的邻居&#xff0c;然后是邻…

DCI-BOX 数据中心互联扩容设备

2U DCI-BOX是针对DCI数据互联开发的一款高性能、大容量DCI平台 恒通未来2U DCI-BOX 优势&#xff1a; 随着5G网络的演进&#xff0c;人们对大数据需求越来越旺盛&#xff0c;2U DCI-BOX是针对DCI数据互联开发的一款高性能、大容量DCI平台。 1. 单机箱最大容量6.4T,单100G功耗…

设计模式——简单工厂模式

设计模式——简单工厂模式 什么是简单工厂模式简单工厂模式的优点 我们今天接着来看设计模式的简单工厂模式&#xff0c;如果还没看过上一篇的单列模式的小伙伴可以点击这里&#xff1a; https://blog.csdn.net/qq_67693066/article/details/136603292 什么是简单工厂模式 简单…

【c语言】结构体的访问

&#x1f388;个人主页&#xff1a;豌豆射手^ &#x1f389;欢迎 &#x1f44d;点赞✍评论⭐收藏 &#x1f917;收录专栏&#xff1a;C语言 &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff0c;让我们共同学习、交流进步&…

宏景eHR customreport/tree SQL注入漏洞复现

0x01 产品简介 宏景eHR人力资源管理软件是一款人力资源管理与数字化应用相融合,满足动态化、协同化、流程化、战略化需求的软件。 0x02 漏洞概述 宏景eHR customreport/tree 接口处存在SQL注入漏洞,未经过身份认证的远程攻击者可利用此漏洞执行任意SQL指令,从而窃取数据库…

【cocos creator】【TS】贝塞尔曲线,地图之间显示曲线,顺着曲线移动

参考&#xff1a; https://blog.csdn.net/Ctrls_/article/details/108731313 https://blog.csdn.net/qq_28299311/article/details/104009804 const { ccclass, property } cc._decorator;ccclass export default class mapPanel extends cc.Component {property(cc.Node)pla…

力扣HOT100 - 41. 缺失的第一个正数

解题思路&#xff1a; 原地哈希 就相当于&#xff0c;让每个数字n都回到下标为n-1的家里。 而那些没有回到家里的就成了孤魂野鬼流浪在外&#xff0c;他们要么是根本就没有自己的家&#xff08;数字小于等于0或者大于nums.size()&#xff09;&#xff0c;要么是自己的家被别…

试题 C: 质因数个数

萎了&#xff0c;整个人都萎了 快三天都没刷题了&#xff0c;想着明天就蓝桥杯了&#xff0c;就找了个真题做了下 可以看得出来这题很简单 但是没有测试点给我用&#xff0c;所以我的代码不保证正确性 代码如下&#xff1a; #include<cstdio> #include<cmath> …

014:vue3 van-list van-pull-refresh实现上拉加载,下拉刷新

文章目录 1. 实现上拉加载&#xff0c;下拉刷新效果2. van-list&#xff0c;van-pull-refresh组件详解2.1 van-list组件2.2 van-pull-refresh组件 3. 完整案例4. 坑点&#xff1a;加载页面会一直调用加载接口 1. 实现上拉加载&#xff0c;下拉刷新效果 通过下拉刷新加载下一页…

20240405,数据类型,运算符,程序流程结构

是我深夜爆炸&#xff0c;不能再去补救C了&#xff0c;真的来不及了&#xff0c;不能再三天打鱼两天晒网了&#xff0c;真的来不及了呜呜呜呜 我实在是不知道看什么课&#xff0c;那黑马吧……MOOC的北邮的C正在进行呜呜 #include <iostream> using namespace std; int…

力扣 | 54. 螺旋矩阵

注意按照顺时针方向进行访问元素&#xff0c;以及每次触发的条件只会满足一个&#xff01; public List<Integer> spiralOrder(int [][] matrix){List<Integer> result new ArrayList<>();int m matrix.length;int n matrix[0].length;int row0,col 0;//…

【汇编】计算机系统构成

计算机系统构成 计算机系统包括硬件和软件两部分 硬件 典型的计算机结构包括 中央处理器(CPU)、存储器和输入输出(I/O)子系统 三个主要组成部分&#xff0c;用系统总线把它们连接在一起 计算机硬件组成与各部分之间的联系 软件 计算机软件可以分为系统软件和用户软件两大类 …

react17中配置webpack:使用@代表src目录

在vue的项目中可以使用表示src目录&#xff0c;使用该符号表示绝对路径&#xff0c;那么在react中想要使用怎么办呢&#xff1f; 在react中使用表示src目录是需要在webpack中配置的&#xff0c;在核心模块node_modules-》react-scripts-》config-》webpack.config.js中搜索找到…

必应bing搜索广告推广国内能开户吗?

随着互联网广告市场的不断进化和细分化&#xff0c;必应Bing搜索广告已逐渐成为中国企业拓展国内市场、精准触达目标客户的重要渠道之一。2024年&#xff0c;必应Bing在国内市场的进一步布局&#xff0c;不仅彰显了其对本土企业的强大吸引力&#xff0c;更带来了全新的开户政策…

Java基础入门--第十一章--JDBC(Java Database Connection)Java数据库连接

JDBC 11.1 什么是JDBC11.1.1 JDBC概述11.1.2 JDBC驱动程序 11.2 JDBC的常用API11.3 JDBC编程11.3.1 JDBC 编程步骤11.3.2 实现第一个JDBC程序 我的MySQL的root密码: root 11.1 什么是JDBC 11.1.1 JDBC概述 JDBC的全称是Java数据库连接&#xff08;Java Database Connectivit…

React - 你知道props和state之间深层次的区别吗

难度级别:初级及以上 提问概率:60% 如果把React组件看做一个函数的话,props更像是外部传入的参数,而state更像是函数内部定义的变量。那么他们还有哪些更深层次的区别呢,我们来看一下。 首先说props,他是组件外部传入的参数,我们知道…

【React】React18+Typescript+craco配置最小化批量引入Svg并应用的组件

React18Typescriptcraco配置最小化批量引入Svg并应用的组件 前言创建React Typescript项目通过require.context实现批量引入Svg安装[types/webpack-env](https://github.com/DefinitelyTyped/DefinitelyTyped/blob/master/README.zh-Hans.md)解决类型报错安装[craco](https://…

数据中心的网络架构设计,打造高效、安全的数字底座

数据中心的网络架构设计 一、数据中心网络架构设计原则 网络,作为数据中心的核心支柱,其结构精妙,由众多二层接入设备与少量三层设备共同编织而成。过去,数据中心网络规模有限,仅凭数十台设备的简单互连便能实现信息的畅通无阻。然而,随着技术与应用需求的飞速增长,数据…