秦怀杂货店

General Store

  • 首页
  • 文章归档
  • 标签
  • 分类
  • 关于页面

  • 搜索
随便聊聊 数据结构 小游戏 数据库 Docker Springboot 系统设计 雪花算法 分布式 海量ip 最长回文子串 算法 面试题 线程池 多线程 线程 java学习 布隆过滤器 github 架构设计 docsify Git JVM LeetCode 杂货思考 设计模式 Lambda native isAssignableFrom 反射 剑指Offer mybatis SPI JDBC 编程工具 Java基础 集合

leetcode【5】-- 最长回文子串(三种解答)

发表于 2021-10-08 | 分类于 LeetCode | 0 | 阅读次数 311

题目描述

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

例子

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

示例 2:
输入:s = "cbbd"
输出:"bb"

示例 3:
输入:s = "a"
输出:"a"

示例 4:
输入:s = "ac"
输出:"a"

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-palindromic-substring,著作权归领扣网络所有。

思路以及解答

暴力破解

暴力破解,即是针对里面每一个子串,都去判断是否为回文串。

判断每一个字符是不是回文串,比如用 cbac 判断,左右两个指针,对称判断,相等则往中间移动,继续判断,不相等则直接返回 false 。

    public static String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }
        String result = s.substring(0, 1);
        for (int i=0; i < s.length() - 1; i++) {
            for (int j = i + 1; j < s.length(); j++) {
                if (judge(s, i, j) && j - i + 1 > result.length()) {
                    result = s.substring(i, j+1);
                }
            }
        }
        return result;
    }
    
    // 判断每个子串是不是回文
    public static boolean judge(String source, int start, int end) {
        // 对称轴对比
        while (start <= end) {
            if (source.charAt(start) != source.charAt(end)) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }

暴力破解复杂度过高,会超时,不推荐使用。

中心拓展法

回文串总是中心对称的,前面使用暴力法的时候,都是截取出子串之后再判断,只有判断到全部对称,才能证明回文,这样其实走了很多弯路,只要最后一个不对称,前功尽弃。

反过来想,我们不如在每一个点,都尝试往两边拓展,这样只要不匹配,就可以及时止顺。

值得注意的是,中心拓展法的中心怎么找?3个字符有多少个中心呢?

一共有五个中心,有些中心可能是两个字符的间隙,有些中心可能是字符。那么设计的时候,我们用 left 和 right 表示两个指针:

  • left = right:对称中心为字符
  • left + 1 = right: 对称中心为两个字符的间隙

具体实现如下:

class Solution {
    // 开始下标
    public static int start = -1;
    // 最大长度
    public static int maxLen= 0;
    public String longestPalindrome(String s) {
        start = -1;
        maxLen = 0;
        if(s==null||s.length()==0){
            return "";
        }
        for(int i=0;i<s.length();i++){
            // 以当前字符为对称轴
            judge(s,i,i);
            // 以当前字符和下一个字符的间隙为对称轴
            judge(s,i,i+1);
        }
        if(start == -1){
            return "";
        }
        return s.substring(start,start+maxLen);
    }

    public void judge(String s,int left,int right){
        while(left>=0 && right<s.length() && s.charAt(left)==s.charAt(right)){
            left--;
            right++;
        }
        int size =  right-left-1;
        if(size > maxLen){
            maxLen = size;
            start = left+1;
        }
    }
}

动态规划

其实,一个字符串是回文串的话,那么它倒过来读也是一样的,也就是说,它与它反转后的字符串,其实是完全匹配的,那么要是我们用一个字符串和它反转字符串一一统计匹配,是不是就可以得到结果呢?

答案是肯定的!假设原字符串为 s1,反转后的字符串为 s2,字符串长度为 n,我们用数组 nums[n][n] 来记录匹配的数量,nums[i][j]表示以 s1[i] 结尾的字符子串,和以 s2[j]结尾的字符子串,两者的匹配字符的最大数值。

  • 当 s1[i] == s2[j]:
    • 如果 i == 0 或者 j == 0: nums[i][j] = 1
    • 否则 nums[i][j] = nums[i - 1][j - 1] + 1;
  • 如果 s1[i] != s2[j],则 nums[i][j]=0

前面说的其实就是状态转移表达式,也就是 nums[i][j] 是怎么求解的?nums[i][j] 是依赖于 nums[i - 1][j - 1] 和 当前字符是否匹配,如果当前字符不匹配,直接赋值为 0,只有在当前字符匹配的情况下,才会需要看前面一位的匹配数值 nums[i - 1][j - 1]。

假设以 babad 为例子:

最后两行的计算:

实现的代码如下:

class Solution {
    public static String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        if (s.length() == 1) {
            return s;
        }
        int len = s.length();
        String s1 = new StringBuffer(s).reverse().toString();
        int[][] nums = new int[len][len];
        int end = 0, max = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums.length; j++) {
                if (s1.charAt(i) == s.charAt(j)) {
                    if (i == 0 || j == 0) {
                        nums[i][j] = 1;
                    } else {
                        nums[i][j] = nums[i - 1][j - 1] + 1;
                    }
                }
                if (nums[i][j] > max) {
                    if (len - i - 1 + nums[i][j] - 1 == j) {
                        end = j;
                        max = nums[i][j];
                    }
                }
            }
        }
        return s.substring(end - max+1, end+1);
    }
}

作者简介

【作者简介】:
秦怀,公众号【秦怀杂货店】作者,技术之路不在一时,山高水长,纵使缓慢,驰而不息。个人写作方向:Java源码解析,JDBC,Mybatis,Spring,redis,分布式,剑指Offer,LeetCode等,认真写好每一篇文章,不喜欢标题党,不喜欢花里胡哨,大多写系列文章,不能保证我写的都完全正确,但是我保证所写的均经过实践或者查找资料。遗漏或者错误之处,还望指正。

剑指Offer全部题解PDF

2020年我写了什么?

开源编程笔记

  • 本文作者: 秦怀杂货店
  • 本文链接: http://aphysia.cn/archives/leetcode5--zui-chang-hui-wen-zi-chuan--san-zhong-jie-da-
  • 版权声明: 本博客所有文章除特别声明外,均采用CC BY-NC-SA 3.0 许可协议。转载请注明出处!
# 随便聊聊 # 数据结构 # 小游戏 # 数据库 # Docker # Springboot # 系统设计 # 雪花算法 # 分布式 # 海量ip # 最长回文子串 # 算法 # 面试题 # 线程池 # 多线程 # 线程 # java学习 # 布隆过滤器 # github # 架构设计 # docsify # Git # JVM # LeetCode # 杂货思考 # 设计模式 # Lambda # native # isAssignableFrom # 反射 # 剑指Offer # mybatis # SPI # JDBC # 编程工具 # Java基础 # 集合
面试题 -- 如何设计一个线程池
100台机器上海量IP如何查找出现频率 Top 100?
  • 文章目录
  • 站点概览
秦怀杂货店

秦怀杂货店

纵然缓慢,驰而不息。

145 日志
19 分类
37 标签
Github E-mail
Creative Commons
0%
© 2022 秦怀杂货店
由 Halo 强力驱动
|
主题 - NexT.Pisces v5.1.4