当前位置: 首页 > 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;...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

HBuilderX安装(uni-app和小程序开发)

下载HBuilderX 访问官方网站&#xff1a;https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本&#xff1a; Windows版&#xff08;推荐下载标准版&#xff09; Windows系统安装步骤 运行安装程序&#xff1a; 双击下载的.exe安装文件 如果出现安全提示&…...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

【Linux手册】探秘系统世界:从用户交互到硬件底层的全链路工作之旅

目录 前言 操作系统与驱动程序 是什么&#xff0c;为什么 怎么做 system call 用户操作接口 总结 前言 日常生活中&#xff0c;我们在使用电子设备时&#xff0c;我们所输入执行的每一条指令最终大多都会作用到硬件上&#xff0c;比如下载一款软件最终会下载到硬盘上&am…...

沙箱虚拟化技术虚拟机容器之间的关系详解

问题 沙箱、虚拟化、容器三者分开一一介绍的话我知道他们各自都是什么东西&#xff0c;但是如果把三者放在一起&#xff0c;它们之间到底什么关系&#xff1f;又有什么联系呢&#xff1f;我不是很明白&#xff01;&#xff01;&#xff01; 就比如说&#xff1a; 沙箱&#…...

Kubernetes 节点自动伸缩(Cluster Autoscaler)原理与实践

在 Kubernetes 集群中&#xff0c;如何在保障应用高可用的同时有效地管理资源&#xff0c;一直是运维人员和开发者关注的重点。随着微服务架构的普及&#xff0c;集群内各个服务的负载波动日趋明显&#xff0c;传统的手动扩缩容方式已无法满足实时性和弹性需求。 Cluster Auto…...

人工智能 - 在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型

在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型。这些平台各有侧重&#xff0c;适用场景差异显著。下面我将从核心功能定位、典型应用场景、真实体验痛点、选型决策关键点进行拆解&#xff0c;并提供具体场景下的推荐方案。 一、核心功能定位速览 平台核心定位技术栈亮…...

DAY 45 超大力王爱学Python

来自超大力王的友情提示&#xff1a;在用tensordoard的时候一定一定要用绝对位置&#xff0c;例如&#xff1a;tensorboard --logdir"D:\代码\archive (1)\runs\cifar10_mlp_experiment_2" 不然读取不了数据 知识点回顾&#xff1a; tensorboard的发展历史和原理tens…...