当前位置: 首页 > news >正文

最长回文子串



问题

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

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

示例 1:

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

示例 2:

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

提示:

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

题解

方法1:动态规划

对于一个子串而言,如果它是回文串,并且长度大于 222,那么将它首尾的两个字母去除之后,它仍然是个回文串。例如对于字符串 “ababa”,如果我们已经知道 “bab” 是回文串,那么 “ababa” 一定是回文串,这是因为它的首尾两个字母都是“a”。

那么我们就可以写出动态规划的状态转移方程:

if len(s)<=2

else

中心扩展算法
  • 确定中心回文子:P(i,j)中心子串是指长度大于等于1的相同字符组成的子串,例如“bab”的“a”,“baab”的“aa”,“baaab”的“aaa”等
  • 从每一种边界情况开始「扩展」,也可以得出所有的状态对应的答案。

class Solution:def longestPalindrome(self, s: str) -> str:max_longest=0max_longest_s=""s_len=len(s)longest=[[0]*s_len for _ in range(s_len)]for i in range(s_len):longest[i][i] = 1left_i,right_i=i-1,i+1while right_i<s_len and s[i]==s[right_i]:longest[i][right_i]=1right_i+=1while left_i>=0 and right_i<s_len:if s[left_i]==s[right_i]:longest[i][right_i] = 1longest[i][left_i] = 1left_i-=1right_i+=1else:breakif right_i-1-left_i-1+1>max_longest:max_longest_s=s[left_i+1:right_i]max_longest=right_i-1-left_i-1+1# print(longest,max_longest_s)return max_longest_s

方法2 Manacher算法

请自学

相关文章:

最长回文子串

问题 给你一个字符串 s&#xff0c;找到 s 中最长的回文子串。 如果字符串的反序与原始字符串相同&#xff0c;则该字符串称为回文字符串。 示例 1&#xff1a; 输入&#xff1a;s "babad" 输出&#xff1a;"bab" 解释&#xff1a;"aba" 同…...

从瀑布模式到水母模式:ChatGPT引领软件研发的革新之路

ChatGPT引领软件研发的革新之路 概述操作建议本书优势 内容简介作者简介专家推荐读者对象目录直播预告写在末尾&#xff1a; 主页传送门&#xff1a;&#x1f4c0; 传送 概述 计算机技术的发展和互联网的普及&#xff0c;使信息处理和传输变得更加高效&#xff0c;极大地改变了…...

一种使用wireshark快速分析抓包文件amr音频流的思路方法

解决方案&#xff1a; 1. 使用wireshark过滤amr,并导出原始数据文件&#xff1b; 2.使用ue的二进制编辑模式&#xff0c;编辑该文件&#xff0c;添加amr头&#xff0c;6个字节数据“#!AMR”&#xff0c;字节数据为 23 21 41 4D 52 0A 3.修正格式&#xff1a;通过抓包发现&#…...

银河麒麟x86版、银河麒麟arm版操作系统编译zlmediakit

脚本 # 安装依赖 gcc-c.x86_64 这个不加的话会有问题 sudo yum -y install gcc gcc-c libssl-dev libsdl-dev libavcodec-dev libavutil-dev ffmpeg git openssl-devel gcc-c.x86_64mkdir -p /home/zenglg cd /home/zenglg git clone --depth 1 https://gitee.com/xia-chu…...

InnoDB - 双写机制

双写机制用于提高数据持久性和可靠性。 双写机制的核心思想是&#xff0c;将写操作先写入一个临时缓冲区&#xff0c;然后再写入实际的数据文件。这个临时缓冲区通常是固定大小的内存缓冲区&#xff0c;称为双写缓冲。这个机制的主要目的是避免数据文件在写入时出现损坏或数据…...

【蓝桥杯选拔赛真题08】C++最大值最小值平均值 青少年组蓝桥杯C++选拔赛真题 STEMA比赛真题解析

目录 C/C++最大值最小值平均值 一、题目要求 1、编程实现 2、输入输出 二、算法分析</...

软考高级系统架构设计师系列之:系统开发基础知识、项目管理、信息安全和网络安全、计算机网络章节选择题详解

软考高级系统架构设计师系列之:系统开发基础知识、项目管理、信息安全和网络安全、计算机网络章节选择题详解 一、产品配置二、需求管理三、需求跟踪四、软件生命周期五、RUP六、耦合与内聚七、软件文档八、软件需求九、软件活动十、项目时间管理十一、需求管理十二、项目范围…...

0基础学习PyFlink——时间滑动窗口(Sliding Time Windows)

在《0基础学习PyFlink——时间滚动窗口(Tumbling Time Windows)》我们介绍了不会有重复数据的时间滚动窗口。本节我们将介绍存在重复计算数据的时间滑动窗口。 关于滑动窗口&#xff0c;可以先看下《0基础学习PyFlink——个数滑动窗口&#xff08;Sliding Count Windows&#x…...

API安全之《大话:API的前世今生》

写在前面&#xff1a;本文结合API使用的业界现状&#xff0c;系统性地阐述API的基本概念、发展历史、表现形式等基础内容&#xff0c;主要包含以下内容&#xff1a; 1.什么是API 2.API的发展历史 3.现代API常用消息格式 4.top N 互联网企业API 使用现状 当前的世界是一个信…...

H5或者Vue实现二维码识别

前言 1、扫码识别库采用开源的zxing/library 2、支持js&#xff0c;Vue&#xff0c;lit等实现 原文章地址和代码仓库地址 1、在界面创建video标签用来显示摄像头内容 <!-- 视区 --><!-- lit写法 --> <video ${ref(this.videoRef)} class"xy-scan-wrap…...

stm32整理(三)ADC

1 ADC简介 1.1 ADC 简介 12 位 ADC 是逐次趋近型模数转换器。它具有多达 19 个复用通道&#xff0c;可测量来自 16 个外部 源、两个内部源和 VBAT 通道的信号。这些通道的 A/D 转换可在单次、连续、扫描或不连续 采样模式下进行。ADC 的结果存储在一个左对齐或右对齐的 16 位…...

Redis-持久化+主从架构

文章目录 Redis的持久化RDB模式异步持久化的实现AOF模式总结 Redis的主从架构1.端口以及文件调试测试2.主从配置3.数据同步原理&#xff08;第一次同步为全局同步&#xff09;4.增量同步5.主从配置优化6.问:master主机怎么判断从机slave是不是第一次同步数据&#xff1f; Redis…...

STM32H750之FreeRTOS学习--------(四)中断管理

四、FreeRTOS中断管理 中断的概念不再过多叙述&#xff0c;学习过逻辑的都知道 中断的执行过程 中断请求 外设产生中断请求&#xff08;GPIO外部中断、定时器中断等&#xff09;响应中断 CPU停止执行当前程序&#xff0c;转而去执行中断处理程序&#xff08;ISR&#xff09;…...

Macroscope安全漏洞检测工具简介

学习目标&#xff1a; 本介绍旨在帮助感兴趣者尽快了解 Macroscope&#xff0c;这是一款用于安全测试自动化和漏洞管理的企业工具。 全覆盖应用程序安全测试&#xff1a; 如下图所示&#xff0c;如果使用多种互补工具&#xff08;SAST/DAST/SCA 等&#xff09;来检测应用程序…...

【Linux】Nignx的入门使用负载均衡动静分离(前后端项目部署)---超详细

一&#xff0c;Nignx入门 1.1 Nignx是什么 Nginx是一个高性能的开源Web服务器和反向代理服务器。它使用事件驱动的异步框架&#xff0c;可同时处理大量请求&#xff0c;支持负载均衡、反向代理、HTTP缓存等常见Web服务场景。Nginx可以作为一个前端的Web服务器&#xff0c;也可…...

【入门Flink】- 04Flink部署模式和运行模式【偏概念】

部署模式 在一些应用场景中&#xff0c;对于集群资源分配和占用的方式&#xff0c;可能会有特定的需求。Flink为各种场景提供了不同的部署模式&#xff0c;主要有以下三种&#xff1a;会话模式&#xff08;Session Mode&#xff09;、单作业模式&#xff08;Per-Job Mode&…...

react面试要点

# React面试知识点 ## React是什么&#xff1f;谈一谈你对react的理解 1 React是一个网页UI库 2 react的特点是 声明式 组件化 通用性 3 react优点&#xff1a; 简单&#xff0c;低耦合高内聚&#xff0c;由于虚拟dom概念&#xff0c;可以做到一次学习到处使用。 …...

在Google Kubernetes集群创建分布式Jenkins(一)

因为项目需要&#xff0c;在GKE的集群上需要创建一个CICD的环境&#xff0c;记录一下安装部署一个分布式Jenkins集群的过程。 分布式Jenkins由一个主服务器和多个Agent组成&#xff0c;Agent可以执行主服务器分派的任务。如下图所示&#xff1a; 如上图&#xff0c;Jenkins Ag…...

【Python全栈_公开课学习记录】

一、初识python (一).Python起源 Python创始人为吉多范罗苏姆&#xff08;荷兰&#xff09;&#xff0c;Python崇尚优美、清晰、简明的编辑风格。Python语言结构清晰简单、数据库丰富、运行成熟稳定&#xff0c;科学计算统计分析领先。目前广泛应用于云计算、Web开发、科学运算…...

uniapp循环列表单选框实现单选

目录 图片源码参考最后 图片 源码 参考 大佬 最后 感觉文章好的话记得点个心心和关注和收藏&#xff0c;有错的地方麻烦指正一下&#xff0c;如果需要转载,请标明出处&#xff0c;多谢&#xff01;&#xff01;&#xff01;...

【WEB模型】CS架构BS架构HTMLCSSJS

一、CS架构 - Client/Server 客户端/服务器pc安装软件&#xff1a;安卓应用、ios应用需要安装专门软件才能用&#xff0c;软件直接跟服务器通信开发成本高&#xff0c;各个平台都有对应的开发工程师好处&#xff1a;功能强大二、BS架构 - Browser/Server 浏览器/服务器不需要安…...

OpenClaw+千问3.5-9B智能家居:自然语言控制HomeAssistant

OpenClaw千问3.5-9B智能家居&#xff1a;自然语言控制HomeAssistant 1. 为什么需要自然语言控制智能家居&#xff1f; 去年装修新房时&#xff0c;我安装了HomeAssistant系统来控制全屋灯光、空调和窗帘。虽然手机App能实现远程控制&#xff0c;但每次都要打开应用、找到对应…...

3分钟拥有自己的零代码平台!敲敲云一键安装全攻略

敲敲云 AI 专题研究 | 敲敲云零代码平台一键部署&#xff0c;让普通人轻松搭建业务系统 还在为技术门槛发愁&#xff1f;还在为复杂的代码开发而烦恼&#xff1f; 今天要给大家介绍一款完全免费的零代码平台 —— 敲敲云。它集成了 AI 应用开发能力&#xff0c;支持一键安装部…...

Windows驱动存储深度管理:从问题诊断到系统优化的完整解决方案

Windows驱动存储深度管理&#xff1a;从问题诊断到系统优化的完整解决方案 【免费下载链接】DriverStoreExplorer Driver Store Explorer [RAPR] 项目地址: https://gitcode.com/gh_mirrors/dr/DriverStoreExplorer 问题发现&#xff1a;驱动管理中的隐形痛点与风险 系…...

魔兽争霸3终极优化指南:如何解锁180fps帧率限制并解决现代硬件兼容性问题

魔兽争霸3终极优化指南&#xff1a;如何解锁180fps帧率限制并解决现代硬件兼容性问题 【免费下载链接】WarcraftHelper Warcraft III Helper , support 1.20e, 1.24e, 1.26a, 1.27a, 1.27b 项目地址: https://gitcode.com/gh_mirrors/wa/WarcraftHelper 魔兽争霸3作为经…...

零基础入门Python爬虫:借助快马AI生成你的第一个可运行爬虫脚本

今天想和大家分享一下我作为Python爬虫新手的学习经历。刚开始接触爬虫时&#xff0c;面对各种库和概念真的有点懵&#xff0c;直到发现了InsCode(快马)平台&#xff0c;它让我用自然语言描述需求就能生成可运行的代码&#xff0c;大大降低了入门门槛。 爬虫的基本原理 爬虫就像…...

Fiji图像处理软件更新故障排查指南:当科学工具遇到“升级烦恼“

Fiji图像处理软件更新故障排查指南&#xff1a;当科学工具遇到"升级烦恼" 【免费下载链接】fiji A "batteries-included" distribution of ImageJ :battery: 项目地址: https://gitcode.com/gh_mirrors/fi/fiji Fiji作为生物图像分析领域的瑞士军刀…...

探索GetQzonehistory:永久保存QQ空间记忆的数字时光机

探索GetQzonehistory&#xff1a;永久保存QQ空间记忆的数字时光机 【免费下载链接】GetQzonehistory 获取QQ空间发布的历史说说 项目地址: https://gitcode.com/GitHub_Trending/ge/GetQzonehistory 在数字时代&#xff0c;我们的记忆分散在各个社交平台&#xff0c;而Q…...

SiameseAOE中文-base高性能部署:WebUI响应<800ms,吞吐达12QPS(RTX4090)

SiameseAOE中文-base高性能部署&#xff1a;WebUI响应<800ms&#xff0c;吞吐达12QPS&#xff08;RTX4090&#xff09; 今天要跟大家聊一个非常实用的工具——SiameseAOE通用属性观点抽取模型。你可能听说过信息抽取&#xff0c;但面对海量文本&#xff0c;如何快速、准确地…...

Pixel Aurora Engine真实案例:用‘蒸汽朋克猫武士’生成整套游戏美术资源

Pixel Aurora Engine真实案例&#xff1a;用蒸汽朋克猫武士生成整套游戏美术资源 1. 项目背景与工具介绍 Pixel Aurora Engine&#xff08;像素极光引擎&#xff09;是一款基于AI扩散模型的高端像素艺术生成工具。它采用复古的8-bit游戏机风格界面&#xff0c;却能产出专业级…...