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

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...