Leetcode刷题java之5. 最长回文子串

迷南。 2023-07-03 08:07 43阅读 0赞

执行结果：

通过

显示详情

执行用时 :12 ms, 在所有 Java 提交中击败了72.89% 的用户

内存消耗 :36.4 MB, 在所有 Java 提交中击败了68.95%的用户

题目：

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"  
输出: "bab"  
注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"  
输出: "bb"

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/longest-palindromic-substring  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

采用中心扩展法，每找到一个更长的，就更新，但是中心有多少个呢，有2n-1个，为什么不是n个呢，因为aba和abba是两种情况，但是他们都是回文串。

代码：

class Solution {
        public String longestPalindrome(String s) {
            if(s==null||s.length()<1)
            {
                return "";
            }
            //采用中心扩展算法
            int start=0;
            int end=0;
            for(int i=0;i<s.length();i++)
            {
                int len1=help(s,i,i);
                int len2=help(s,i,i+1);
                int len=Math.max(len1,len2);
                if(len>end-start)
                {
                    start=i-(len-1)/2;
                    end=i+len/2;
                }
            }
            //取子字符串后面的string的s是小写的
            return s.substring(start,end+1);
        }
        public int help(String s,int left,int right)
        {
            while(left>=0&&right<=s.length()-1&&s.charAt(left)==s.charAt(right))
            {
                left--;
                right++;
            }
            return right-left-1;
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，43人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode5.最长回文子串

目录题目链接题目分析解题思路暴力中心向两边拓展搜索题目链接 [链接]

水深无声/ 2024年03月25日 23:37/ 0 赞/ 138 阅读

相关 LeetCode-5. 最长回文子串

目录题目思路动态规划题目来源 [5. 最长回文子串][5.] 题目思路本题和[LeetCode-647. 回文子串][Le

﹏ヽ暗。殇╰゛Y/ 2024年03月24日 13:18/ 0 赞/ 173 阅读

相关 Leetcode刷题java之5. 最长回文子串

执行结果：通过显示详情执行用时 :12 ms, 在所有 Java 提交中击败了72.89% 的用户内存消耗 :36.4 MB, 在所有 Java 提交中击败了6

迷南。/ 2023年07月03日 08:07/ 0 赞/ 44 阅读

相关最长回文子串(leetcode5)

求一个字符串的最长回文子串，我们可以将以每个字符为首的子串都遍历一遍，判断是否为回文，如果是回文，再判断最大长度的回文子串。算法简单，但是算法复杂度太高，O（n^3）

小咪咪/ 2023年06月03日 14:53/ 0 赞/ 128 阅读

相关 LeetCode-5 最长回文子串

[LeetCode5][] 做法主要有三种：暴力搜索中心扩散法马拉车Manacher 暴力搜索和中心扩散法O(n^2) Manacher是O

﹏ヽ暗。殇╰゛Y/ 2022年12月08日 14:16/ 0 赞/ 265 阅读

相关 leetcode5最长回文子串

![在这里插入图片描述][20210602112131449.png] 思路：（1）使用dp\[i\]\[j\]来进行s\[i\]~s\[j\]子串是否为回文子串的标

布满荆棘的人生/ 2022年10月17日 10:40/ 0 赞/ 278 阅读

相关 Leetcode 5. 最长回文子串

题目重述给你一个字符串 s，找到 s 中最长的回文子串。示例 1：输入：s = “babad” 输出：“bab” 解释：“aba” 同样是符合题意的

灰太狼/ 2022年09月01日 00:59/ 0 赞/ 362 阅读

相关【LeetCode】5. 最长回文子串

题目链接：[https://leetcode-cn.com/problems/longest-palindromic-substring/description/][https

比眉伴天荒/ 2022年05月03日 00:28/ 0 赞/ 374 阅读

相关 LeetCode-5.最长回文子串

题目给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。示例 1： > 输入: “babad” > 输出: “bab”

本是古典何须时尚/ 2022年01月31日 00:29/ 0 赞/ 373 阅读

相关 LeetCode（5）：最长回文子串

给定一个字符串 `s`，找到 `s` 中最长的回文子串。你可以假设 `s` 的最大长度为 1000。 ![20190809152320317.png][] 解法 1: 暴

淩亂°似流年/ 2021年11月06日 00:44/ 0 赞/ 527 阅读