力扣5.最长回文子串

题目描述

在这里插入图片描述

思路

1.能够反复利用已判断好的回文子串

2.当子串s[i+1,j-1]是回文子串时,只要s[i]==s[j],那么s[i,j]也会是回文子串

3.用好动态规划,具体解释在代码注释里

代码

class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        //如果是单字符,必定是回文,直接返回s
        if(len < 2) return s;
        //dp[][]表示s[i,...,j]是否是回文
        boolean[][] dp = new boolean[len][len];
        //最长回文子串长度初始化为1
        int maxLen = 1;
        //最长回文子串左边界初始化为0
        int begin = 0;
        char[] ch = s.toCharArray();
        //先进行初始化,所有单个字符都是回文
        for(int i = 0;i < len;i++){
            dp[i][i] = true;
        }
        //j是右边界
        for(int j = 1;j < len;j++){
            //i是左边界
            for(int i = 0;i < len;i++){
                //如果左边界大于右边界,就退出循环
                if(i > j){
                    break;
                }
                if(ch[i] != ch[j]){
                    dp[i][j] = false;
                }else{
                    //假如子串两边都相等,中间只有一个字母,直接返回状态true
                    if(j - i < 3){
                        dp[i][j] = true;
                    }else{
                        //不然当前状态就由上一个子串决定,是由内向外的,假如s[2,3]是回文,s[1]==s[4],
                        //那么s[1,4]也是回文;反之如果s[2,3]不是回文,那s[1,4]也不会是回文
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
                //当dp[i][j]为true且回文子串长度大于最长长度,就更新最长回文子串长度
                if(dp[i][j] && j - i + 1 > maxLen){
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin,begin + maxLen);
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/207603.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【【FPGA 之Micro Blaze的串口中断实验】】

FPGA 之Micro Blaze的串口中断实验 我们在使用 MicroBlaze 进行嵌入式系统设计的时候&#xff0c;通常会用到 AXI Uartlite IP 核与外部设备通信。AXI UART IP 核实现了 RS-232 通讯协议&#xff0c;并使得大家可以设置串口通信相关的波特率、奇偶校验位、停止位和数据位等参数…

一看就懂的RxJava源码分析

一看就懂的RxJava源码分析 前言零、观察模式简介一、RxJava使用示例一二、示例一源码分析0. 示例一代码分解1. RxJava中的观察者是谁&#xff1f;2. RxJava中的被观察者又是谁&#xff1f;3. 观察者又是如何安插到被观察者中的&#xff1f;4. 示例一RxJava源码整体关系类图4. R…

一本书读懂数据治理

企业数据治理非常必要&#xff0c;它是企业实现数字化转型的基础&#xff0c;是企业的一个顶层策略&#xff0c;一个管理体系&#xff0c;也是一个技术体系&#xff0c;涵盖战略、组织、文化、方法、制度、流程、技术和工具等多个层面的内容。 数据治理不是对“数据”的治理&am…

Unity 与 虚拟机ROS连接

Unity 与 虚拟机ROS连接 知识储备前期准备ROS部分Unity部分 连接测试 知识储备 unity官方教程&#xff1a; https://github.com/Unity-Technologies/Unity-Robotics-HubWin11家庭版开启HyperV&#xff1a; https://zhuanlan.zhihu.com/p/577980646HyperV安装Ubuntu: https://b…

SQL Sever 基础知识 - 数据查询

SQL Sever 基础知识 - 一、查询数据 一、查询数据第1节 基本 SQL Server 语句SELECT第2节 SELECT语句示例2.1 SELECT - 检索表示例的某些列2.2 SELECT - 检索表的所有列2.3 SELECT - 对结果集进行筛选2.4 SELECT - 对结果集进行排序2.5 SELECT - 对结果集进行分组2.5 SELECT - …

浅学指针(4)函数指针数组和qsort的使用

系列文章目录 文章目录 系列文章目录前言1.函数指针数组的⽤途作用&#xff1a;可以让代码更简洁&#xff0c;逻辑更清晰 2. 回调函数回调函数就是⼀个通过函数指针调⽤的函数 3 . qsort函数qsort函数可以排序所有数据类型解释如图&#xff1a;![在这里插入图片描述](https://i…

【高效开发工具系列】Hutool DateUtil工具类

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…

Leetcode-二叉树oj题

1.二叉树的前序遍历 144. 二叉树的前序遍历https://leetcode.cn/problems/binary-tree-preorder-traversal/这个题目在遍历的基础上还要求返回数组&#xff0c;数组里面按前序存放二叉树节点的值。 既然要返回数组&#xff0c;就必然要malloc一块空间&#xff0c;那么我们需…

Spring简单的存储和读取

前言 前面讲了spring的创建&#xff0c;现在说说关于Bean和五大类注解 一、Bean是什么&#xff1f; 在 Java 语⾔中对象也叫做 Bean&#xff0c;所以后⾯咱们再遇到对象就以 Bean 著称。这篇文章还是以spring创建为主。 二、存储对象 2.1 俩种存储方式 需要在 spring-conf…

作用域和作用域链

前端面试大全JavaScript作用域和作用域链 &#x1f31f;经典真题 &#x1f31f;作用域&#xff08;Scope&#xff09; 什么是作用域 全局作用域和函数作用域 块级作用域 &#x1f31f;作用域链 什么是自由变量 什么是作用域链 关于自由变量的取值 &#x1f31f;作用域…

初识Linux:权限

目录 提示&#xff1a;以下指令均在Xshell 7 中进行 Linux 的权限 内核&#xff1a; 查看操作系统版本 查看cpu信息 查看内存信息 外部程序&#xff1a; 用户&#xff1a; 普通用户变为超级用户&#xff1a; su 和 su-的区别&#xff1a; root用户变成普通用户&#…

【matlab程序】画海洋流场

【matlab程序】画海洋流场 clear;clc; file ( ‘0227.nc’); latncread(file,‘latitude’); lonncread(file,‘longitude’); uncread(file,‘water_u’); vncread(file,‘water_v’); [x,y]meshgrid(lon,lat); xx’; yy’; interval4; figure (1) set(gcf,‘color’,[1 1 1…

【linux】基本指令(上篇)

1.快速认识5~6个指令 pwd指令 ls指令 touch指令 cd指令 clear指令 touch指令 详细讲解 首先有一个问题就是当我们创建一个文件&#xff0c;但是没有往里面写内容&#xff0c;那么磁盘上会有该文件吗&#xff1f; 磁盘上会保存&#xff0c;因为创建好的文件&#xff0c;没有…

【古月居《ros入门21讲》学习笔记】05_ROS是什么及其核心概念

目录 说明 1. ROS发展史 ROS版本演变 2. ROS是什么 ROS中的通信机制 ROS中的开发工具 ROS中的应用功能 ROS中的生态系统 3. ROS核心概念 节点与节点管理器 通信方式1&#xff1a;话题 通信方式2&#xff1a;服务 话题与服务的区别 参数 文件系统 说明 1. 本系列…

学习笔记7——数据库基础知识以及mysql的查询语句

学习笔记系列开头惯例发布一些寻亲消息 链接&#xff1a;https://baobeihuijia.com/bbhj/contents/3/199913.html 数据库 三个概念区分 DB&#xff1a;数据库&#xff0c;存储数据的仓库&#xff0c;有组织的数据容器DBMS:数据库管理系统SQL&#xff1a;几乎所有的DBMS都支持…

从PDF和图像中提取文本,以供大型语言模型使用

想法 大型语言模型已经席卷了互联网&#xff0c;导致更多的人没有认真关注使用这些模型最重要的部分&#xff1a;高质量的数据&#xff01;本文旨在提供一些有效从任何类型文档中提取文本的技术。 Python库 本文专注于Pytesseract、easyOCR、PyPDF2和LangChain库。实验数据是一…

jQuery的使用

目录 jquery对象&#xff1a; jquery作为一般函数调用参数: jquery事件机制 jquery dom操作 jquery对象&#xff1a; <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" cont…

MySQL 教程 1.4

MySQL 连接 使用mysql二进制方式连接 您可以使用MySQL二进制方式进入到mysql命令提示符下来连接MySQL数据库。 实例 以下是从命令行中连接mysql服务器的简单实例&#xff1a; [roothost]# mysql -u root -p Enter password:****** 在登录成功后会出现 mysql> 命令提示窗…

Python全栈之基本数据类型详解

文章目录 1.注释2.输出3.变量4.命名规范5.变量的定义方式1.字符串类型2.数字类型3.List列表类型4.tuple 元组类型的定义5.Dict字典类型6.set集合类型7.数据类型转换8.自动类型转换9.强制类型转换关于Python技术储备一、Python所有方向的学习路线二、Python基础学习视频三、精品…

Reactor网络线程模型

目录 传统下网络服务模型 事件监听模型 NIO核心概念 单线程Reactor模式 多线程Reactor模式 Kafka 的网络设计 主要概念 类比思维理解 参考文章 传统下网络服务模型 线程太多无法处理大规模请求 事件监听模型 NIO核心概念 nio是实现reactor模式的底层API代码 单…