LeetCode算法之最长回文子串(中心扩展算法)

系统管理员 2022-04-24 08:04 221阅读 0赞

一.题目

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
    示例 1：
    输入: "babad"
    输出: "bab"
    注意: "aba" 也是一个有效答案。
    示例 2：
    输入: "cbbd"
    输出: "bb"

二.代码及思想

class Solution {
        public String longestPalindrome(String s) {
            if (s == null || s.length() < 1) return "";
            int start = 0, end = 0;
            for (int i = 0; i < s.length(); i++) {
                int len1 = expandAroundCenter(s, i, i);    //回文子串的长度为奇数时
                int len2 = expandAroundCenter(s, i, i + 1);    //回文子串的长度为偶数时
                int len = Math.max(len1, len2);        //取两种情况中的最大值
                if (len > end - start) {                //满足该条件则为当前的最长回文子串
                    start = i - (len - 1) / 2;
                    end = i + len / 2;
                }
            }
            return s.substring(start, end + 1);
        }
    
        private int expandAroundCenter(String s, int left, int right) {
            int L = left, R = right;
            while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
                L--;
                R++;    
            }
            return R - L - 1;
        }
    }

我们观察到回文中心的两侧互为镜像.因此,回文可以从它的中心展开,并且只有2n-1个这样的中心.

你可能会问,为什么会是2n-1个,而不是n个中心?原因在于所含字母数为偶数的回文的中心可以出与两字母之间(例如"abba"的中心在两个'b'之间).

发表评论取消回复

表情：

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

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

相关阅读

相关最长回文(manacher算法,最大回文子串)

Problem Description 给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度. 回文就是正反读都是一样的字符串,如aba,

刺骨的言语ヽ痛彻心扉/ 2024年02月17日 19:27/ 0 赞/ 93 阅读

相关 [Java·算法·中等]LeetCode5. 最长回文子串

每天一题，防止痴呆题目示例分析思路1 题解1 分析思路2 题解2 题目给你一个字符串 `s`，找到 `s` 中最长的回

小鱼儿/ 2023年09月24日 20:49/ 0 赞/ 50 阅读

相关算法面试题：最长回文子串

leetcode算法题目：给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000 public static void main

一时失言乱红尘/ 2023年05月28日 11:14/ 0 赞/ 53 阅读

相关算法：最长回文子串。

给定一个字符串 `s`，找到 `s` 中最长的回文子串。你可以假设 `s` 的最大长度为 1000。示例 > 输入: "babad" > 输出: "b

àì夳堔傛蜴生んèń/ 2023年02月24日 03:57/ 0 赞/ 56 阅读

相关【LeetCode】最长回文子串

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

刺骨的言语ヽ痛彻心扉/ 2023年02月14日 13:03/ 0 赞/ 51 阅读

相关算法题：最长回文子串

算法题：最长回文子串题目描述示例 python代码执行效率题目描述给定一个字符串 s，找到 s 中最长的回文子串。你可以假

布满荆棘的人生/ 2022年12月27日 08:43/ 0 赞/ 254 阅读

相关算法：最长回文子串长度

动态规划：最长回文子串：连续+回文公式 p\[i,j\] = 1)if(str\[i\] == str\[j\]) p\[i\]\[j\] = 2+p\[

冷不防/ 2022年07月26日 00:06/ 0 赞/ 274 阅读

相关 LeetCode算法之最长回文子串(中心扩展算法)

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

系统管理员/ 2022年04月24日 08:04/ 0 赞/ 222 阅读

相关 leetcode 5-最长回文子串(中心扩展算法)

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

青旅半醒/ 2022年01月15日 20:29/ 0 赞/ 204 阅读

相关 LeetCode：最长回文子串

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

快来打我*/ 2021年11月22日 15:20/ 0 赞/ 416 阅读