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 s
        max_len, begin = 1,0
        dp = [[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] = 1
                    else:
                        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 = L
                    begin = i
        return 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, 1
        for i in range(n):
            dp[i][i] = 1
        for L in range(2, n+1):
            for i in range(n):
                j = L + i - 1
                if j >= n:
                    break
                if s[i] == s[j]:
                    if j - i < 3:
                        dp[i][j] = 1
                    else:
                        dp[i][j] = dp[i+1][j-1]
                if dp[i][j] and L > max_len:
                    begin = i
                    max_len = L
        return s[begin: begin + max_len]

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

解题思路三:0


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

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

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

相关文章

kubernetes应用的包管理工具---Helm的安装、部署、构建Helm Chart、分发

kubernetes应用的包管理工具—Helm的安装、部署、构建Helm Chart、分发 文章目录 kubernetes应用的包管理工具---Helm的安装、部署、构建Helm Chart、分发1. 引入Helm的原因1.1 没有使用Helm的部署1.2 使用Helm部署 2. Helm核心概念3. Helm架构3.1 V2版本3.2 V3版本 4. Helm安装…

品牌百度百科词条创建多少钱?

百度百科作为国内最具权威和影响力的知识型平台&#xff0c;吸引了无数品牌和企业争相入驻。一个品牌的百度百科词条&#xff0c;不仅是对品牌形象的一种提升&#xff0c;更是增加品牌曝光度、提高品牌知名度的重要途径。品牌百度百科词条创建多少钱&#xff0c;这成为了许多企…

基于SpringBoot+Vue的高校会议室预定管理系统(源码+文档+部署+讲解)

一.系统概述 伴随着我国社会的发展&#xff0c;人民生活质量日益提高。于是对系统进行规范而严格是十分有必要的&#xff0c;所以许许多多的信息管理系统应运而生。此时单靠人力应对这些事务就显得有些力不从心了。所以本论文将设计一套高校会议室预订管理系统&#xff0c;帮助…

【电控笔记0】拉式转换与转移函数

概要 laplace&#xff1a;单输入单输出&#xff0c;线性系统 laplace 传递函数 总结

python+appium调@pytest.mark.parametrize返回missing 1 required positional argument:

出错描述&#xff1a; 1、在做pythonappium自动化测试时&#xff0c;使用装饰器pytest.mark.parametrize&#xff08;“参数”&#xff0c;[值1&#xff0c;值2&#xff0c;值3]&#xff09;&#xff0c;测试脚本执行返回test_xx() missing 1 required positional argument:“…

Mybatis generate xml 没有被覆盖

添加插件即可 <plugin type"org.mybatis.generator.plugins.UnmergeableXmlMappersPlugin"/>

ssm040安徽新华学院实验中心管理系统的设计与实现+jsp

实验中心管理系统 摘 要 本安徽新华学院实验中心管理系统的设计目标是实现安徽新华学院实验中心的信息化管理&#xff0c;提高管理效率&#xff0c;使得安徽新华学院实验中心管理工作规范化、科学化、高效化。 本文重点阐述了安徽新华学院实验中心管理系统的开发过程&#x…

libcurl 简单实用

LibCurl是一个开源的免费的多协议数据传输开源库&#xff0c;该框架具备跨平台性&#xff0c;开源免费&#xff0c;并提供了包括HTTP、FTP、SMTP、POP3等协议的功能&#xff0c;使用libcurl可以方便地进行网络数据传输操作&#xff0c;如发送HTTP请求、下载文件、发送电子邮件等…

蓝桥杯python速成

总写C&#xff0c;脑子一热&#xff0c;报了个Python&#xff08;有一点想锤死自己&#xff09;&#xff0c;临时抱佛脚了 1.list的插入删除 append extend insert&#xff08;在索引位插入99&#xff09;---忘记用法别慌&#xff0c;用help查询 remove&#xff08;去掉第一个3…

mysql题目2

tj11: select sex,count(sex) from t_athletes group by sex; tj12: select name 姓名,TIMESTAMPDIFF(year,birthday,2024-1-1) 年龄 from t_athletes tj13: SELECT * FROM t_athletesWHERE id NOT IN (SELECT aid FROM t_match WHERE sid IN (SELECT id FROM t_sport WHE…

510天,暴雪竞品迎来大考

北京时间4月10日&#xff0c;暴雪娱乐、微软游戏与网易正式宣布重新达成合作。两则数据值得关注&#xff1a; 一是上午暴雪与网易刚宣布合作&#xff0c;中午《魔兽世界》玩家预约就超过了20W。 截图时间为中午12:48 二是在上午10:24&#xff0c;《炉石传说》官方公众号发布回…

直播视频传输处理技术

流程 在视频直播场景中&#xff0c;从拍摄到手机用户接收的整个过程涉及多个技术环节&#xff1a; 视频采集&#xff1a; 视频源通常来自摄像机或智能手机摄像头&#xff0c;通过捕捉连续的画面生成原始视频信号。 编码压缩&#xff1a; 为了减少数据量以适应网络传输&#x…

一个比 Celery 轻量好用的异步任务工具

文章目录 1、RQ安装2、RQ基本概念2.1、Queue2.2、Job2.3、Worker 3、RQ 高级用法3.1、自定义任务失败处理3.2、任务依赖关系3.3、定时任务 4、RQ web 界面5、查看任务结果6、RQ 与 celery 对比7、总结 Python RQ&#xff08;Redis Queue&#xff09;是一个轻量级的异步任务队列…

c++取经之路(其五)——类和对象拷贝构造函数

概念&#xff1a;拷贝构造函数&#xff0c;只有单个形参&#xff0c;该形参是对本类类型对象的引用(一般常用const修饰)&#xff0c;在用已存在的类类型对象创建新对象时由编译器自动调用。 特征&#xff1a; 1. 拷贝构造函数是构造函数的一个重载形式 如&#xff1a; 2. 拷贝…

最强ChatGPT Plus发布!碾压Claude!ChatGPT5即将发布!

原文链接&#xff1a;ChatGPT发布最新版本&#xff01;新版GPT-4 Turbo重回王座&#xff01;碾压Claude 那个聪明、强大的 ChatGPT&#xff0c;终于又回来了&#xff01; ChatGPT也能用上最强的GPT-4 Turbo了&#xff01;今天&#xff0c;新版GPT-4 Turbo再次重夺大模型排行榜…

Java后端平台的搭建

后端开发准备工作(配置Tomcat) 安装tomcat安装jdk 配置JAVA HONE(到java目录),path(到 bin 目录)解压Tomcat进入到bin目录,双击startup.bat启动tomcat访问 ip端口在conf目录的 server.xml配置端口 后端平台的搭建 创建Web项目(前提搭建好Tomcat配置) 注:一定要提前配置好Ma…

在Ubuntu上安装Docker Compose

Docker Compose 是一个用于定义和管理Docker容器的工具&#xff0c;它使用yml来配置应用的服务、网络和卷等。特别是在定义多个容器时&#xff0c;它非常擅长定义多个容器之间的关系和依赖。 第一步&#xff1a;更新软件包 sudo apt update第二步&#xff1a;安装网络工具cur…

iOS开发如何更改xcode中的Apple ID

在Xcode中更改Apple ID是一项常见的任务&#xff0c;尤其是当你需要切换到另一个开发者账号或者团队时。下面是一个简单的步骤指南&#xff0c;帮助你更改Xcode中的Apple ID&#xff1a; 步骤一&#xff1a;退出当前的Apple ID 1.打开Xcode应用程序。 2.在菜单栏中&#xff0c;…

Rust面试宝典第2题:逆序输出整数

题目 写一个方法&#xff0c;将一个整数逆序打印输出到控制台。注意&#xff1a;当输入的数字含有结尾的0时&#xff0c;输出不应带有前导的0。比如&#xff1a;123的逆序输出为321&#xff0c;8600的逆序输出为68&#xff0c;-609的逆序输出为-906。 解析 这道题本身并没有什么…

C++数据结构与算法——动态规划子序列系列

C第二阶段——数据结构和算法&#xff0c;之前学过一点点数据结构&#xff0c;当时是基于Python来学习的&#xff0c;现在基于C查漏补缺&#xff0c;尤其是树的部分。这一部分计划一个月 (2024.1.30-2024.4.10已完结&#xff09;&#xff0c;任务量确实有点大&#xff0c;包括春…