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

leetCode刷题 5.最长回文子串

目录

1. 思路

2. 解题方法

3. 复杂度

4. Code


题目:

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

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

示例 1:

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

示例 2:

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

提示:

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

1. 思路

        要找到字符串 s 中的最长回文子串,我们可以尝试不同的方法。一种常见的方法是使用动态规划。我们定义一个二维数组 dp,其中 dp[i][j] 表示从索引 i 到索引 j 的子串是否是回文串。根据动态规划的思想,我们可以从长度较短的子串开始,逐步扩展到长度较长的子串,并记录下最长的回文子串。

2. 解题方法

  1. 定义一个二维数组 dp,其中 dp[i][j] 表示从索引 i 到索引 j 的子串是否是回文串。
  2. 初始化 dp 数组,所有长度为 1 的子串都是回文串,相邻字符相同的子串也是回文串。
  3. 遍历字符串,根据动态规划的定义填充 dp 数组。
  4. 在计算 dp 数组的过程中,记录下最长的回文子串的起始位置和长度。
  5. 返回最长的回文子串。

3. 复杂度

  • 时间复杂度:O(n^2),其中 n 是字符串的长度。动态规划需要填充一个二维数组,每个位置需要 O(1) 的时间复杂度。
  • 空间复杂度:O(n^2),需要一个二维数组来存储动态规划的结果。

4. Code

class Solution {public String longestPalindrome(String s) {if (s == null || s.length() < 1) return "";int n = s.length();// 定义二维数组 dp,dp[i][j] 表示从索引 i 到索引 j 的子串是否是回文串boolean[][] dp = new boolean[n][n];int start = 0, maxLength = 1;// 初始化 dp 数组,所有长度为 1 的子串都是回文串for (int i = 0; i < n; i++) {dp[i][i] = true;}// 遍历字符串,计算 dp 数组for (int len = 2; len <= n; len++) {for (int i = 0; i <= n - len; i++) {int j = i + len - 1;// 如果当前子串的头尾字符相同,并且内部子串也是回文串,则当前子串是回文串if (s.charAt(i) == s.charAt(j) && (len == 2 || dp[i + 1][j - 1])) {dp[i][j] = true;// 更新最长回文子串的起始位置和长度if (len > maxLength) {start = i;maxLength = len;}}}}// 返回最长回文子串return s.substring(start, start + maxLength);}
}

        这段代码使用动态规划的方法,实现了找到字符串中最长的回文子串。通过填充一个二维数组 dp,记录从每个位置开始到每个位置结束的子串是否是回文串,并根据动态规划的结果找到最长的回文子串。

欢迎大家后台联系讨论。

相关文章:

leetCode刷题 5.最长回文子串

目录 1. 思路 2. 解题方法 3. 复杂度 4. Code 题目&#xff1a; 给你一个字符串 s&#xff0c;找到 s 中最长的回文子串。 如果字符串的反序与原始字符串相同&#xff0c;则该字符串称为回文字符串。 示例 1&#xff1a; 输入&#xff1a;s "babad" 输出&#x…...

计算机组成原理面试题

计算机组成原理是计算机科学的基础课程之一&#xff0c;涉及计算机系统的基本结构和工作原理。以下是一些可能出现在面试中的计算机组成原理相关题目&#xff1a; 1. **什么是冯诺依曼体系结构&#xff1f;** - 冯诺依曼体系结构是一种计算机组织架构&#xff0c;它将程序指…...

「Mybatis深入三」:高级查询-模糊查询

一、需求 根据username 模糊查询user 表 二、代码演示 1、方式1 数据库环境 CREATE DATABASE mybatis_db; USE mybatis_db; CREATE TABLE user (id INT(11) NOT NULL AUTO_INCREMENT,username VARCHAR(32) NOT NULL COMMENT 用户名称,birthday DATETIME DEFAULT NULL COMMEN…...

LabVIEW管道缺陷智能检测系统

LabVIEW管道缺陷智能检测系统 管道作为一种重要的输送手段&#xff0c;其安全运行状态对生产生活至关重要。然而&#xff0c;随着时间的推移和环境的影响&#xff0c;管道可能会出现老化、锈蚀、裂缝等多种缺陷&#xff0c;这些缺陷若不及时发现和处理&#xff0c;将严重威胁到…...

java在cmd中乱码的问题解决

本文深入探讨了在使用 Java 命令行&#xff08;cmd&#xff09;时可能出现的中文乱码问题&#xff0c;并提供了两种解决方案。首先&#xff0c;通过临时的方式&#xff0c;用户可以执行命令 chcp 936 选择字符集&#xff0c;然后再运行 Java 命令&#xff0c;确保在选择字符集过…...

OpenHarmony教程指南—ArkUI中组件、通用、动画、全局方法的集合

介绍 本示例为ArkUI中组件、通用、动画、全局方法的集合。 本示例使用 Tabs容器组件搭建整体应用框架&#xff0c;每个 TabContent内容视图 使用 div容器组件 嵌套布局&#xff0c;在每个 div 中使用 循环渲染 加载此分类下分类导航数据&#xff0c;底部导航菜单使用 TabCont…...

第二证券|金价逼近历史高点 黄金股价值有望重估

经过两个多月的震荡后&#xff0c;黄金打响新一波攻势&#xff0c;期货商场价格已逼近前史高点。 有分析认为&#xff0c;虽然黄金价格短期已有显着涨幅&#xff0c;存在震荡或许&#xff0c;但中长时间看&#xff0c;跟着美联储钱银政策的转向&#xff0c;黄金价格仍有上行动…...

关于51单片机晶振定时问题

单片机中晶振频率为12MHZ的机器周期怎么算? 1、系统晶振频率是12M&#xff0c;则机器周期&#xff1d;12&#xff0f;12&#xff1d;1us&#xff1b; 2、定时1ms&#xff1d;1&#xff0a;1000&#xff1d;1000us&#xff1b; 3、工作在方式1下&#xff1a;最大计数值是2&a…...

NoSQL--2.MongoDB配置(Windows版)

目录 2.MongdoDB配置 2.1 Windows环境下操作 2.1.1 注册MongDB Atlas&#xff1a; 2.1.2 MongoDB Community Server Download&#xff1a; 2.1.3 启动MondgoDB服务&#xff1a; 2.1.3.1 命令行参数的方式启动MongoDB服务&#xff1a; 2.1.3.2 使用配置文件方式启动Mongo…...

HTML静态网页成品作业(HTML+CSS)——安徽宣笔设计制作(5个页面)

&#x1f389;不定期分享源码&#xff0c;关注不丢失哦 文章目录 一、作品介绍二、作品演示三、代码目录四、网站代码HTML部分代码 五、源码获取 一、作品介绍 &#x1f3f7;️本套采用HTMLCSS&#xff0c;未使用Javacsript代码&#xff0c;共有6个页面。 &#x1f3f7;️想要…...

MySQL CTEs通用表表达式:进阶学习-递归查询

MySQL CTEs通用表表达式&#xff1a;进阶学习-递归查询 递归通用表表达式是其会引用自身的通用表表达式。 CTEs 递归通用表表达式补上了MySQL8之前无法使用递归查询的空白。在之前&#xff0c;递归查询需要使用函数等方法实现。 基础使用&#xff0c;请参考前文&#xff1a; …...

[Java安全入门]二.序列化与反序列化

一.概念 Serialization&#xff08;序列化&#xff09;是一种将对象以一连串的字节描述的过程&#xff1b;反序列化deserialization是一种将这些字节重建成一个对象的过程。将程序中的对象&#xff0c;放入文件中保存就是序列化&#xff0c;将文件中的字节码重新转成对象就是反…...

Dutree:Linux 文件系统磁盘使用追踪工具

在 Linux 系统中&#xff0c;对文件系统的磁盘使用情况进行跟踪和管理是至关重要的。dutree 是一个功能强大的工具&#xff0c;它能够以可视化的方式展示文件系统中的目录和文件的大小&#xff0c;帮助用户更好地了解磁盘空间的使用情况。本文将介绍 dutree 工具的使用方法、功…...

http和https的区别是什么?

–前言 传输信息安全性不同、连接方式不同、端口不同、证书申请方式不同 一、传输信息安全性不同 1、http协议&#xff1a;是超文本传输协议&#xff0c;信息是明文传输。如果攻击者截取了Web浏览器和网站服务器之间的传输报文&#xff0c;就可以直接读懂其中的信息。 2、h…...

学习Android的第十九天

目录 Android ExpandableListView 分组列表 ExpandableListView 属性 ExpandableListView 事件 ExpandableListView 的 Adapter 范例 参考文档 Android ViewFlipper 翻转视图 ViewFlipper 属性 ViewFlipper 方法 为 ViewFlipper 加入 View 例子&#xff1a;全屏幕可…...

C#上位机调试经验

1.使用Visual Studio的远程工具 因为上位机软件安装在工控机上&#xff0c;不方便调试。如果直接把代码放在工控机上&#xff0c;又不太安全。 可以在工控机上安装一个Visual Studio的远程工具&#xff0c;把随身带的笔记本电脑通过网线插在工控机上 这样可以在笔记本上使用…...

BUUCTF---[极客大挑战 2019]BabySQL1

1.这道题和之前做的几道题是相似的&#xff0c;这道题考的知识点更多。难度也比之前的大一些 2.尝试万能密码 or 1#发现过滤了or,使用1和1,发现他对单引号也进行了过滤。于是我尝试进行双写绕过&#xff0c;发现可以通过了。 3.由之前的做题经验可知&#xff0c;这道题会涉及到…...

0基础跨考计算机|408保姆级全年计划

我也是零基础备考408&#xff01; 虽说是计算机专业&#xff0c;但是本科一学期学十几门,真的期末考试完脑子里什么都不进的...基本都是考前一周发疯学完水过考试...&#x1f605; 想要零基础跨考可以直接从王道开始&#xff01;跟教材一点一点啃完全没必要&#x1f978; 现在…...

C# 操作LiteDB

1、很简单的东西不废话&#xff0c;直接上图上代码。 2、NuGet程序中根据自己的项目版本安装LiteDB,如下图&#xff1a; 3、程序运行加过如下图&#xff1a; 4、程序代码如下&#xff1a; using System; using System.Collections.Generic; using System.Linq; using System…...

LeetCode 2917.找出数组中的 K-or 值:基础位运算

【LetMeFly】2917.找出数组中的 K-or 值&#xff1a;基础位运算 力扣题目链接&#xff1a;https://leetcode.cn/problems/find-the-k-or-of-an-array/ 给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。 nums 中的 K-or 是一个满足以下条件的非负整数&#xff1a; 只有…...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

线程与协程

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

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)

设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile&#xff0c;新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

【笔记】WSL 中 Rust 安装与测试完整记录

#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统&#xff1a;Ubuntu 24.04 LTS (WSL2)架构&#xff1a;x86_64 (GNU/Linux)Rust 版本&#xff1a;rustc 1.87.0 (2025-05-09)Cargo 版本&#xff1a;cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别

【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而&#xff0c;传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案&#xff0c;能够实现大范围覆盖并远程采集数据。尽管具备这些优势&#xf…...