算法43：动态规划专练（最长回文子串 力扣5题）---范围模型

之前写过一篇最长回文子序列的博客算法27：最长回文子序列长度（力扣516题）——样本模型 + 范围模型-CSDN博客

在那一篇博客中，回文是可以删除某些字符串组成的。比如：

字符串为：a1b3c4fdcdba， 那么最长回文子序列就是 abccba。长度为6。

本题为力扣第5题：最长回文子串

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

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

示例 1：

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

示例 2：

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

解释一下，如果字符串为 abc121dmcba. 那么最长回文子序列为 abc121cba. 而最长回文子串则为：121.  子串必须是连续的。

一眼看上去就是范围模型。而范围模型就是要讨论样本数据的开头和结尾的情况：

1. 如果字符串为空，那么回文为空字符

2. 如果字符长度为1， 回文子串就为字符串本身

3. 如果字符串长度2， 则字符串下标0和1的字符进行比较，相等则为字符串本身；不等的话，返回其中一个字符即可。这是我在提交代码的时候，力扣提示错误的时候发现的。

为什么要单独讨论长度为 1 和 2 的情况？

因为, 范围模型讨论数据的开头和结尾。如果原始字符串长度为2，则直接走上方的3逻辑； 可如果一个很长的字符串，经过不断的递归以后，最终长度为2的时候，这就比较麻烦了。

比如 *******ab****的时候，你就不能随意返回一个字符作为回文了。

如果你返回a, 那么字符串为mnfabbbbbbbbb. 那你肯定是错误的

如果你返回b，那么字符串为mnfaaaaaaaaabb， 那你肯定也是错的。

回文，就是整体与子串的关系

其实，最长回文子串，最难的就是连续子串的判断。

012345
acddck

字符串为 acddck, 下标1和下标4相等，都为c.  如果下标从1到4 是回文。 那么他的子串

下标2到3也必须是回文才行。这才是判断的核心点。 而下方的推导表格，完全符合。

比如这个字符串为abdddfm。那么二维表格为：

我用x代表空字符串

a (0)b (1)d (2)d (3)d (4)f (5)m (6)
a (0)aX
b (1)bX
d (2)ddd
d (3)ddd
d (4)dX
f (5)fX
m (6)m

由下往上，由左往右推算：

我用x代表空字符串

a (0)b (1)d (2)d (3)d (4)f (5)m (6)
a (0)aXd 类推 类推 类推 类推
b (1)bX   类推 类推 类推
d (2)ddd

 

 前dd,

左下d，

下为dd

当前下标与下标2的字符相等。下标 2到4的子串为 3到3。 而3行3列是回文并且回文为d。

那么 d + d + d = ddd

 类推 类推
d (3)ddd

 前dd,

左下d，

下为空字符

f不等于下标3的d。

取最长的 dd

 类推
d (4)dXX
f (5)fX
m (6)m

最终的二维表就是

a (0)b (1)d (2)d (3)d (4)f (5)m (6)
a (0)aXbddddddddddd
b (1)bXddddddddddd
d (2)dddddddddddd
d (3)ddddddd
d (4)dXX
f (5)fX
m (6)m

直观的看，最长回文字符就是 ddd.

下面贴出递归代码：

package code04.动态规划专项训练03;

/**
 * 力扣 5 题 ： 最长回文子串
 * https://leetcode.cn/problems/longest-palindromic-substring/description/?envType=study-plan-v2&envId=dynamic-programming
 */
public class LongestPalindrome_01 {

    public String longestPalindrome(String s) {

        if (s == null || s.isEmpty()) {
            return "";
        }

        if (s.length() == 1) {
            return s;
        }

        if (s.length() ==  2) {
            return s.charAt(0) == s.charAt(1) ? s : String.valueOf(s.charAt(0));
        }
        char[] ss = s.toCharArray();
        return help(ss, 0, ss.length -1);
    }

    //样本对应模型: 就是从后往前讨论样本数据的末尾下标无限可能。此处的末尾下标应该为0；
    public String help(char[] ss, int index1,  int index2)
    {
        //只有一个字符
        if (index1 == index2) {
            return  String.valueOf(ss[index1]);
        }

        //两个字符
        if (index1 == index2 - 1) {
            String temp = "";
            if (ss[index1] == ss[index2]) {
                temp = String.valueOf(ss[index1]) + String.valueOf(ss[index2]);
            }
            return temp;
        }

        //index2不作为结尾，index作为开头
        String p1 = help(ss, index1, index2 - 1);
        //index2作为结尾，index1不作为开头
        String p2 = help(ss, index1 + 1, index2);
        //index2不作为结尾，index1 不作为开头
        String p3 = help(ss, index1 + 1, index2 - 1);
        //index2作为结尾， index1 作为开头
        String p4 = ss[index1] == ss[index2] ? help(ss, index1 + 1, index2 - 1) : "";
        if (!"".equals(p4) && (index2 - index1 - 1) == p4.length()) {
            p4 =  String.valueOf(ss[index1]) + p4 + String.valueOf(ss[index2]);
        }

        String result =  p1.length() > p2.length() ? p1 : p2;
        result = result.length() > p3.length() ? result : p3;
        result = result.length() > p4.length() ? result : p4;

        return result;
    }

    public static void main(String[] args) {

        //String s= "bab";
        //String s= "babad";
        //String s = "ac";
        //String s= "cbbd";
        //String s= "abdka";
        String s= "aacabdkacaa";
        LongestPalindrome_01 ss = new LongestPalindrome_01();
        System.out.println(ss.longestPalindrome(s));
    }
}

动态规划：

package code04.动态规划专项训练03;

/**
 * 力扣 5 题 ： 最长回文子串
 * https://leetcode.cn/problems/longest-palindromic-substring/description/?envType=study-plan-v2&envId=dynamic-programming
 */
public class LongestPalindrome_01_opt {

    public String longestPalindrome(String s) {

        if (s == null || s.isEmpty()) {
            return "";
        }

        if (s.length() == 1) {
            return s;
        }

        if (s.length() == 2) {
            return s.charAt(0) == s.charAt(1) ? s : s.substring(0,1);
        }

        char[] ss = s.toCharArray();

        int size = ss.length;
        //二维动态规划表，列数多构建1
        String[][] dp = new String[size][size];
        //构建dp的斜线
        for (int i = 0; i < s.length() - 1; i++) {
            //只构建斜线上方部分. 由递归的if (index1 == index2) 得到
            dp[i][i] = String.valueOf(ss[i]);
            //由递归的if (index1 == index2 - 1)得到。递归中还特出判断了length == 2 即原始数组长度为2的
            //情况。但是，动态规划中原始数组长度为2在上方代码已经判断过了。因此，此处只需要关注通用逻辑即可
            dp[i][i+1] =  ss[i] == ss[i + 1] ? String.valueOf(ss[i]) + String.valueOf(ss[i+1]) : "";
        }
        //最后一行最后一列比较特殊，会出现数组越界，因此单独构造
        dp[size - 1][size - 1] = String.valueOf(ss[size - 1]);

        //行，从倒数第3行开始，由下放上推； 因为倒数第1、2行上方代码已经推算出来了
        for (int index1 = size - 3; index1 >= 0; index1--) {
            //列，由左往右推。 这个地方的 index2 = index1 + 2需要看图理解
            for (int index2 = index1 + 2; index2 < size; index2++) {

                //index2不作为结尾，index作为开头
                String p1 = dp[index1][index2 - 1];
                //index2作为结尾，index1不作为开头
                String p2 = dp[index1 + 1][index2];
                //index2不作为结尾，index1 不作为开头
                String p3 = dp[index1 + 1][index2 - 1] != null ? dp[index1 + 1][index2 - 1] : "";

                //index2作为结尾， index1 作为开头
                String p4 = ss[index1] == ss[index2] ? dp[index1 + 1][index2 - 1] : "";
                //特殊处理一下p4为null的情况
                p4 = p4 == null ? "" : p4;
                if (!"".equals(p4) && (index2 - index1 - 1) == p4.length()) {
                    p4 =  String.valueOf(ss[index1]) + p4 + String.valueOf(ss[index2]);
                }

                String result =  p1.length() > p2.length() ? p1 : p2;
                result = result.length() > p3.length() ? result : p3;
                result = result.length() > p4.length() ? result : p4;

                dp[index1][index2] = result;
            }
        }
        return dp[0][size -1];
    }



    public static void main(String[] args) {

        //String s= "bab";
        //String s= "babad";
        //String s = "ac";
        //String s= "cbbd";
        //String s= "abdka";
        String s= "aacabdkacaa";
        //String s= "abbcccbbbcaaccbababcbcabca";
        LongestPalindrome_01_opt ss = new LongestPalindrome_01_opt();
        System.out.println(ss.longestPalindrome(s));
    }
}

测试结果：

测试结果很不理想。速度慢，而且还吃内存，吃内存的主要原因就是动态规划的二维表是字符串类型的。

看了看力扣官方的思想，确实相当不错。下面直接说一下官方的解题思路。

1. 官方并不存储字符串，而是存一个flag，标记回文范围.

a (0)b (1)d (2)d (3)d (4)f (5)m (6)
a (0)truefalse
b (1)truefalse
d (2)truetrue
d (3)truetrue
d (4)truefalse
f (5)truefalse
m (6)true

力扣官方定义了一个最长回文子串的开始位置，beginIndex，长度length

从倒数第3行开始，依旧是由下往上，由左往右推算

a (0)b (1)d (2)d (3)d (4)f (5)m (6)
a (0)truefalsefalsefalsefalsefalsefalse
b (1)truefalsefalsefalsefalsefalse
d (2)truetrue

d == d，并且

子串 3行3列也是回文

整体是回文。

开始位置为2，

长度为3

falsefalse
d (3)truetrue

d != f

false

m != d

false

d (4)truefalse

d ！= m

false

f (5)truefalse
m (6)true

最后，就是根据上方的推算结果进行字符串截图。知道了开始位置，截取字符的长度，问题自然就解决了。

代码如下：

package code04.动态规划专项训练03;

/**
 * 力扣 5 题 ： 最长回文子串
 * https://leetcode.cn/problems/longest-palindromic-substring/description/?envType=study-plan-v2&envId=dynamic-programming
 */
public class LongestPalindrome_01_opt2_1 {

    public String longestPalindrome(String s) {

        if (s == null || s.isEmpty()) {
            return "";
        }

        if (s.length() == 1) {
            return s;
        }

        if (s.length() == 2) {
            return s.charAt(0) == s.charAt(1) ? s : s.substring(0,1);
        }

        char[] ss = s.toCharArray();
        int size = ss.length;


        //默认开始下标为最后一行的最后一列
        int beginIndex = size -1;
        //默认回文长度为1
        int length = 1;

        //二维动态规划表，列数多构建1
        boolean[][] dp = new boolean[size][size];
        //构建dp的斜线
        for (int i = 0; i < s.length(); i++) {
            //只构建斜线上方部分. 由递归的if (index1 == index2) 得到
            dp[i][i] = true;
        }

        //行，从倒数第2行开始，由下放上推； 因为倒数第1行上方代码已经推算出来了
        for (int index1 = size - 2; index1 >= 0; index1--) {
            //列，由左往右推。 当前行的剩余列
            for (int index2 = index1 + 1; index2 < size; index2++) {

                //长度为2. 开头、结尾相等就是回文
                if (index1 == index2 - 1) {
                    //开头、结尾相等。那么 [index1, index2] 就是回文
                    dp[index1][index2] =  ss[index1] == ss[index2] ? true : false;
                }
                else {
                    dp[index1][index2] =  ss[index1] == ss[index2] ? dp[index1 + 1][index2 -1] : false;
                }
                // [index1, index2] 的个数就是 index2 - index1 + 1；
                if( dp[index1][index2] && index2 - index1 + 1 > length) {
                    beginIndex = index1;
                    length = index2 - index1 + 1;
                }
            }
        }

        return s.substring(beginIndex, beginIndex + length);
    }



    public static void main(String[] args) {


        //String s= "bab";
         //String s= "babad";
        //String s = "ac";
         String s= "cbbd";
        //String s= "abdka";
         //String s= "aacabdkacaa";

        //String s= "abbcccbbbcaaccbababcbcabca";
        LongestPalindrome_01_opt2_1 ss = new LongestPalindrome_01_opt2_1();
        System.out.println(ss.longestPalindrome(s));
    }
}

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

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

相关文章

Typora旧版链接（Win+Mac+Linux版）

Typora旧版链接（Win+Mac+Linux版）

记得点赞本文&#xff01;&#xff01;&#xff01; 链接&#xff1a;https://pan.baidu.com/s/1IckUvQUBzQkfHNHXla0zkA?pwd8888 提取码&#xff1a;8888 –来自百度网盘超级会员V7的分享
阅读更多...
JavaWeb—— SpringBootWeb综合案例（登录功能、登录校验、异常处理）

JavaWeb—— SpringBootWeb综合案例（登录功能、登录校验、异常处理）

案例-登录认证 目录 案例-登录认证1. 登录功能1.1 需求1.2 接口文档1.3 思路分析1.4 功能开发1.5 测试 2. 登录校验2.1 问题分析2.2 会话技术2.2.1 会话技术介绍2.2.2 会话跟踪方案2.2.2.1 方案一 - Cookie2.2.2.2 方案二 - Session2.2.2.3 方案三 - 令牌技术 2.3 JWT令牌2.3.1…
阅读更多...
JS 对象数组排序方法测试

JS 对象数组排序方法测试

输出 一.Array.prototype.sort() 1.默认排序 sort() sort() 方法就地对数组的元素进行排序&#xff0c;并返回对相同数组的引用。默认排序是将元素转换为字符串&#xff0c;然后按照它们的 UTF-16 码元值升序排序。 由于它取决于具体实现&#xff0c;因此无法保证排序的时…
阅读更多...
Zookeeper基础入门-1【集群搭建】

Zookeeper基础入门-1【集群搭建】

Zookeeper基础入门-1【集群搭建】 一、Zookeeper 入门1.1.概述1.2.Zookeeper工作机制1.3.Zookeeper特点1.4.数据结构1.5.应用场景1.5.1.统一命名服务1.5.2.统一配置管理1.5.3.统一集群管理1.5.4.服务器动态上下线1.5.5.软负载均衡 1.6.Zookeeper官网1.6.1.Zookeeper下载1.6.2.历…
阅读更多...
软考56-上午题-【数据库】-数据库设计步骤2

软考56-上午题-【数据库】-数据库设计步骤2

一、回顾&#xff1a;数据库设计的步骤 1、用户需求分析&#xff1a;手机用户需求&#xff0c;确定系统边界&#xff1b; 2、概念设计&#xff08;概念结构设计&#xff09;&#xff1a;是抽象概念模型&#xff0c;较理想的是采用E-R方法。 3、逻辑设计&#xff1a;E-R图——…
阅读更多...
带你了解 JavaScript 中的对象

带你了解 JavaScript 中的对象

带你了解 JavaScript 中的对象 基本概念 对象指的就是一个具体的事物&#xff0c;在JavaScript中, 字符串, 数值, 数组, 函数都是对象 每个对象中包含若干的属性和方法 属性: 事物的特征 方法: 事物的行为 1.使用字面量创建对象 使用{ }创建对象 属性和方法使用键值对的形式…
阅读更多...
linux高级编程：线程（二）、进程间的通信方式

linux高级编程：线程（二）、进程间的通信方式

线程&#xff1a; 回顾线程&#xff08;一&#xff09;&#xff1a; 1.线程间通信问题 线程间共享同一个资源&#xff08;临界资源&#xff09; 互斥&#xff1a; 排他性访问 linux系统 -- 提供了Posix标准的函数库 -- 互斥量&#xff08;互斥锁&#xff09; 原子操作&#x…
阅读更多...
1.1 简述卷积的基本操作，卷积和全连接层的区别？

1.1 简述卷积的基本操作，卷积和全连接层的区别？

1.1 简述卷积的基本操作&#xff0c;卷积和全连接层的区别&#xff1f; 摘要&#xff1a; 全连接层的输出层每个节点与输入层的所有节点连接。 卷积层具有局部连接和权值共享的特性。 问题&#xff1a;简述卷积的基本操作&#xff0c;并分析其与全连接层的区别。 分析与解答&a…
阅读更多...
【计算机网络】深度学习HTTPS协议

【计算机网络】深度学习HTTPS协议

&#x1f493; 博客主页&#xff1a;从零开始的-CodeNinja之路 ⏩ 收录文章&#xff1a;【计算机网络】深度学习HTTPS协议 &#x1f389;欢迎大家点赞&#x1f44d;评论&#x1f4dd;收藏⭐文章 目录 一:HTTPS是什么二:HTTPS的工作过程三:对称加密四:非对称加密五:中间人攻击1…
阅读更多...
JAVA内存模型与JVM内存结构

JAVA内存模型与JVM内存结构

注意区分Java内存模型&#xff08;Java Memory Model&#xff0c;简称JMM&#xff09;与Jvm内存结构&#xff0c;前者与多线程相关&#xff0c;后者与JVM内部存储相关。本文会对两者进行简单介绍。 一、JAVA内存模型(JMM) 1. 概念 说来话长&#xff0c;由于在不同硬件厂商和…
阅读更多...
详解动态规划（算法村第十九关青铜挑战）

详解动态规划（算法村第十九关青铜挑战）

不同路径 62. 不同路径 - 力扣&#xff08;LeetCode&#xff09; 一个机器人位于一个 m x n 网格的左上角 &#xff08;起始点在下图中标记为 “Start” &#xff09;。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角&#xff08;在下图中标记为 “Finis…
阅读更多...
重载（Overload）和重写（Override）的区别。重载的方法能否根据返回类型进行区分？

重载（Overload）和重写（Override）的区别。重载的方法能否根据返回类型进行区分？

大家好我是苏麟 , 今天开始又一个专栏开始了(又一个坑 哈哈) . 重载&#xff08;Overload&#xff09;和重写&#xff08;Override&#xff09;的区别。重载的方法能否根据返回类型进行区分&#xff1f; 方法的重载和重写都是实现多态的方式&#xff0c;区别在于前者实现的是编…
阅读更多...
pyqt5怎么返回错误信息给页面（警告窗口）

pyqt5怎么返回错误信息给页面（警告窗口）

在软件设计中&#xff0c;我们可能会遇到对异常的处理&#xff0c;有些异常是用户需要看到的&#xff0c;比如说&#xff0c;当我们登录出错的时候&#xff0c;后端需要给我们返回响应的错误信息&#xff0c;就像下图实现的这样。 类似这种效果&#xff0c;我们该如何实现&…
阅读更多...
C++真题列表

C++真题列表

题目解析&#xff1a;RAM是闪存&#xff0c;只要一关机一拔电&#xff0c;就会丢失数据 题目解答&#xff1a;A 题目解析&#xff1a;TXT格式是文本文档 题目解答&#xff1a;B 题目解析&#xff1a;IP地址中每一个字节的取值范围是[0~255]&#xff0c;是不可能有256的 题目…
阅读更多...
2024最新算法：美洲狮优化算法（Puma Optimizar Algorithm ，POA）求解23个基准函数（提供MATLAB代码）

2024最新算法：美洲狮优化算法（Puma Optimizar Algorithm ，POA）求解23个基准函数（提供MATLAB代码）

一、美洲狮优化算法 美洲狮优化算法&#xff08;Puma Optimizar Algorithm &#xff0c;POA&#xff09;由Benyamin Abdollahzadeh等人于2024年提出&#xff0c;其灵感来自美洲狮的智慧和生活。在该算法中&#xff0c;在探索和开发的每个阶段都提出了独特而强大的机制&#xf…
阅读更多...
TDengine 在 DISTRIBUTECH 分享输配电数据管理实践

TDengine 在 DISTRIBUTECH 分享输配电数据管理实践

2 月 27-29 日&#xff0c;2024 美国国际输配电电网及公共事业展&#xff08;DISTRIBUTECH International 2024&#xff09;在美国-佛罗里达州-奥兰多国家会展中心举办。作为全球领先的年度输配电行业盛会&#xff0c;也是美洲地区首屈一指的专业展览会&#xff0c;该展会的举办…
阅读更多...
干货！Python获取字典元素

干货！Python获取字典元素

1.访问字典中的元素 第一种方式&#xff1a;通过key访问 dict1 {"name":"中国医生", "author":"刘伟强", "person":"张涵予"} print(dict1["author"]) # 刘伟强 # print(dict1["price"…
阅读更多...
八. 实战：CUDA-BEVFusion部署分析-分析BEVFusion中各个ONNX

八. 实战：CUDA-BEVFusion部署分析-分析BEVFusion中各个ONNX

目录 前言0. 简述1. camera.backbone.onnx(fp16)2. camera.backbone.onnx(int8)3. camera.vtransform.onnx(fp16)4. fuser.onnx(fp16)5. fuser.onnx(int8)6. lidar.backbone.xyz.onnx7. head.bbox.onnx(fp16)总结下载链接参考 前言 自动驾驶之心推出的《CUDA与TensorRT部署实战…
阅读更多...
ArrayList集合源码分析

ArrayList集合源码分析

ArrayList集合源码分析 文章目录 ArrayList集合源码分析一、字段分析二、构造方法分析三、方法分析四、总结 内容如有错误或者其他需要注意的知识点&#xff0c;欢迎指正或者探讨补充&#xff0c;共同进步。 一、字段分析 //默认初始化容量。这里和Vector一样&#xff0c;只是…
阅读更多...
Maven实战（2）之搭建maven私服

Maven实战（2）之搭建maven私服

一, 背景: 如果使用国外镜像,下载速度比较慢; 如果使用阿里云镜像,速度还算OK,但是假如网速不好的时候,其实也是比较慢的; 如果没有网的情况下更加下载不了. 二, 本地仓库、个人/公司私服、远程仓库关系如下: 三, 下载安装nexus私服 略
阅读更多...
最新文章

Copyright @ 2022~2023