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

OpenClaw学习助手方案:Qwen2.5-VL-7B解析教材插图生成记忆卡片

OpenClaw学习助手方案&#xff1a;Qwen2.5-VL-7B解析教材插图生成记忆卡片 1. 为什么需要AI辅助学习工具 去年备考专业认证时&#xff0c;我发现自己总在重复低效的学习循环——花大量时间手动整理教材图表中的关键数据&#xff0c;再誊写到Anki卡片上。这种机械劳动不仅耗时…...

多层PCB内部结构与HDI技术深度解析

1. 多层PCB内部结构全解析作为一名硬件工程师&#xff0c;第一次拆解十层PCB板时&#xff0c;那种震撼感至今难忘。密密麻麻的过孔像微型城市的地下管网&#xff0c;精密排布的走线如同错综复杂的立体交通网。今天我就用最直观的立体解剖图&#xff0c;带你看透各种叠层结构的P…...

新手入门:零基础借助快马生成你的第一个openmaic网页版调用程序

今天想和大家分享一个特别适合新手入门的实践项目——如何借助InsCode(快马)平台快速生成你的第一个openmaic网页版调用程序。作为一个刚接触AI开发的新手&#xff0c;我最初看到各种API文档和代码示例时也是一头雾水&#xff0c;但通过这个可视化工具&#xff0c;居然半小时就…...

LCC-HVDC系统中交流滤波器的选型实战:从理论到工程落地

LCC-HVDC系统中交流滤波器的选型实战&#xff1a;从理论到工程落地 在特高压直流输电工程中&#xff0c;交流滤波器如同电力系统的"净化器"&#xff0c;其选型直接关系到电网谐波抑制效果与系统运行经济性。某800kV换流站曾因滤波器选型不当导致年度损耗增加1200万元…...

StreamlabsArduinoAlerts:嵌入式设备接入Twitch直播事件

1. StreamlabsArduinoAlerts 库深度解析&#xff1a;嵌入式设备接入 Twitch 直播事件的完整实现方案 StreamlabsArduinoAlerts 是一个专为资源受限嵌入式平台设计的轻量级 C 库&#xff0c;其核心目标是让 Arduino、ESP8266、ESP32、Particle 及基于 ATmega/STM32 的 MCU 能够直…...

YOLO12应用场景:零售货架识别中商品计数+品类分类一体化方案

YOLO12应用场景&#xff1a;零售货架识别中商品计数品类分类一体化方案 1. 引言&#xff1a;零售货架管理的痛点与新解法 如果你经营过一家便利店、超市&#xff0c;或者负责过零售门店的运营&#xff0c;一定对“货架盘点”这件事深有感触。每到月底或者需要补货时&#xff…...

N_m3u8DL-CLI-SimpleG:快速下载M3U8视频的终极指南

N_m3u8DL-CLI-SimpleG&#xff1a;快速下载M3U8视频的终极指南 【免费下载链接】N_m3u8DL-CLI-SimpleG N_m3u8DL-CLIs simple GUI 项目地址: https://gitcode.com/gh_mirrors/nm3/N_m3u8DL-CLI-SimpleG N_m3u8DL-CLI-SimpleG是一个专门用于下载M3U8流媒体视频的开源工具…...

实用指南:如何通过Energy Star X轻松提升Windows 11电池续航40%

实用指南&#xff1a;如何通过Energy Star X轻松提升Windows 11电池续航40% 【免费下载链接】EnergyStarX &#x1f50b; Improve your Windows 11 devices battery life. A WinUI 3 GUI for https://github.com/imbushuo/EnergyStar. 项目地址: https://gitcode.com/gh_mirr…...

EmbeddingGemma-300m部署指南:Ollama镜像+Prometheus监控+日志追踪一体化

EmbeddingGemma-300m部署指南&#xff1a;Ollama镜像Prometheus监控日志追踪一体化 想快速搭建一个功能强大、易于管理的文本向量化服务吗&#xff1f;EmbeddingGemma-300m作为谷歌推出的轻量级嵌入模型&#xff0c;凭借其3亿参数和出色的性能&#xff0c;是构建本地语义搜索、…...

3步实现HTML到Word的智能转换:html-to-docx技术深度解析

3步实现HTML到Word的智能转换&#xff1a;html-to-docx技术深度解析 【免费下载链接】html-to-docx HTML to DOCX converter 项目地址: https://gitcode.com/gh_mirrors/ht/html-to-docx 你是否曾遇到过这样的场景&#xff1f;精心设计的网页报告需要转换为Word文档进行…...