5. 最长回文子串

《二哥的 LeetCode 刷题笔记》真的容易懂。

————————by 鲁迅

题意

给你一个字符串 s，找到 s 中最长的回文子串。如果字符串的反序与原始字符串相同，则

该字符串称为回文字符串。

示例

输入：s = "babad"

输出："bab"

解释："aba" 同样是符合题意的答案。

难度

中等

分析 1

要解这道题，我们需要搞清楚几个概念：

• 什么是字符串的反序？

• 什么是回文串？

• 什么是最长回文子串？

首先，字符串的反序就是将字符串中的字符顺序颠倒过来，例如：abc 的反序就是 cba。

其次，回文串就是正着看和反着看是一样的字符串，例如：abcba 就是一个回文串，因为

反着看也是 abcba。

最后，最长回文子串就是在一个字符串中，最长的回文串，例如：abcba 的最长回文子串

就是 abcba，而示例中的 babad 的最长回文子串就是 bab 或者 aba。

那搞清楚这几个概念后，我们就很容易想到暴力解法：截取每一段子串，然后判断它是不

是回文串，如果是的话，就更新最长回文子串。

class Solution {

// 辅助函数，用于检查字符串 s 中从索引 begin 到 end 的子串是否为回文

boolean isPalindrome(String s, int begin, int end) {

while (begin <= end) {

// 如果两端的字符不同，则不是回文

if (s.charAt(begin) != s.charAt(end))

return false;

// 向中间移动

begin++;

end--;

}

 // 如果所有字符都相同，则是回文

return true;

}

// 主函数，用于找出字符串 s 中的最长回文子串

public String longestPalindrome(String s) {

int ansl = 0, ansr = 0; // 存储最长回文子串的起始和结束索引

// 外层循环遍历子串的起始位置

for (int i = 0; i < s.length(); i++)

// 内层循环遍历子串的结束位置

for (int j = i; j < s.length(); j++)

// 检查子串是否是回文

if (isPalindrome(s, i, j)) {

// 如果找到更长的回文子串，则更新最长回文子串的索引

if (j - i > ansr - ansl) {

ansr = j;

ansl = i;

}

}

// 返回最长回文子串

return s.substring(ansl, ansr + 1);

}

}

但是，结果非常感人……

005.%E6%9C%80%E9%95%BF%E5%9B%9E%E6%96%87%E5%AD%90%E4%B8%B2-

20231217172237.png

完全无法接受的结果，两层循环 $ O(n^2) $ 的时间复杂度，再加上判断回文串又是 $ O(n)

$ 的时间复杂度，所以总共是 $ O(n^3) $ 的时间复杂度，这完完全全超出了题目预期的范

围。

分析 2

我们来想想其他的方法。

“回文串”，意思就是正着看和反着看是一样的。

那我们是不是能够通过求这个字符串倒置之后的串和原串的最长公共子串，得到的这个最

长公共子串，也就是原串的最长回文子串？

是的，见下图。

005.%E6%9C%80%E9%95%BF%E5%9B%9E%E6%96%87%E5%AD%90%E4%B8%B2-

20231217172912.png

但是有一个问题。

例如：adccdcda，它倒置之后是 adcdccda，两个串的最长公共子串则是 adc 或者 cda，

可是这两个显然不是回文子串。

问题就出在位置的判断上。

除了要判断是不是最长公共子串，还需要多一个判断，看看这个最长公共子串在原串中的

位置和倒置之后的串中的位置是不是对应的。

求解两个字符串的最长公共子串，我们可以用动态规划来解决。

什么是动态规划？

动态规划（Dynamic programming，简称 DP）是一种在数学、计算机科学和经济学中使

用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。常常适用于有

重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于暴力解法。

简单来说，动态规划其实就是，给定一个问题，我们把它分解成若干个子问题，直到子问

题可以直接求解，然后再逐步合并子问题的解，最终得到原问题的解。

动态规划的核心思想就是记住已经解决过的子问题的解，避免重复计算。

来看一个比较经典的例子：

• Q：1+1+1+1+1=？

• A：5

• Q：在等号左边再+1 呢？

• A：6

• Q：你怎么这么快就知道答案了？

• A：我记住了，1+1+1+1+1=5，再+1 就是 6 了。

这就是动态规划的核心思想，记住已经解决过的子问题的解，避免重复计算。

再来看一个更经典的例子：斐波那契数列。

斐波那契数列是这样一个数列：1、1、2、3、5、8、13、21、34、……，即第一项和第

二项为 1，第三项为前两项之和，第四项为前两项之和，以此类推。

我们可以用递归的方式来求解斐波那契数列，但是递归的方式会有很多重复计算，例如：

求解第 5 项的时候，需要先求解第 4 项和第 3 项，求解第 4 项的时候，需要先求解第 3 项

和第 2 项，求解第 3 项的时候，需要先求解第 2 项和第 1 项；求解第 4 项的时候，需要先

求解第 3 项和第 2 项，求解第 3 项的时候，需要先求解第 2 项和第 1 项；求解第 3 项的时

候，需要先求解第 2 项和第 1 项；求解第 2 项的时候，需要先求解第 1 项；求解第 1 项的

时候，直接返回 1。

用代码表示就是这样的：

class Solution {

// 递归求解斐波那契数列

public int fib(int n) {

if (n == 1 || n == 2)

return 1;

return fib(n - 1) + fib(n - 2);

}

}

那如果用动态规划的方式来求解斐波那契数列呢？

我们可以用一个数组来存储已经求解过的子问题的解，这样就可以避免重复计算了。

class Solution {

// 动态规划求解斐波那契数列

public int fib(int n) {

int[] f = new int[n + 1];

f[1] = f[2] = 1;

for (int i = 3; i <= n; i++)

f[i] = f[i - 1] + f[i - 2];

return f[n];

}

}

大家可以感受一下递归和动态规划两种方式求解斐波那契数列的不同。

递归是，以前哪怕计算过，比如说求第 4 项的时候已经计算过第 3 项了，但是求第 5 项的

时候还是要重新计算第 3 项，这就是重复计算。

但动态规划是，以前计算过的结果我都保留下来，下次用到的时候直接拿来用，不用重新

计算。比如说求第 4 项的时候已经计算过第 3 项了，求第 5 项的时候直接拿第 4 项和第 3

项的结果相加就可以了。

OK，相信大家都明白了动态规划的内核了。

如果还需要补充资料，可以看看这个帖子，里面还会讲到贪心和动态规划的区

别，讲的很好：https://www.zhihu.com/question/23995189/answer/

613096905

那我们来继续解这道题。

第一步，反转原始字符串 s，得到字符串 rev。

第二步，使用一个二维数组 f[][] 来记录 s 和 rev 之间的最长公共子串的长度。f[i][j] 表示

s 中以 i 结尾和 rev 中以 j 结尾的子串的最长公共后缀的长度。

对二维数组比较陌生的球友可以先看一下《二哥的 Java 进阶之路》中这篇内

容：掌握 Java 二维数组

第三步，填充动态规划表，遍历这两个字符串，对于每一对字符 s[i] 和 rev[j]：

• 如果 s[i] == rev[j]，则 f[i][j] = f[i-1][j-1] + 1。这表示当前字符匹配，并且可以在

之前的最长公共后缀上增加一个字符。

• 否则，f[i][j] 保持为 0。

第四步，检查回文条件，在填充表的过程中，每次 f[i][j] 被更新时，我们需要检查是否满

足回文条件。

即检查以 i 结尾的 s 的子串是否真的是一个回文串，通过检查 f[i][j] 对应的子串的起始位

置是否正确。如果 f[i][j] 是回文，并且是到目前为止找到的最长的，我们更新最长回文子

串的长度和起始位置。

最后，根据记录的最长长度和起始位置，从原始字符串 s 中提取出最长的回文子串。

class Solution {

public String longestPalindrome(String s) {

// 反转原始字符串

String rev = new StringBuffer(s).reverse().toString();

int n = s.length();

// 动态规划数组，f[i][j] 存储 s[0...i] 和 rev[0...j] 的最长公共子串长度

int[][] f = new int[n][n];

// 记录最长回文子串的长度和起始位置

int maxLen = 1;

 int begPos = 0;

// 初始化第一列

for (int j = 0; j < n; j++)

if (rev.charAt(j) == s.charAt(0))

f[0][j] = 1;

// 动态规划填表

for (int i = 1; i < n; i++) {

// 初始化第一行

f[i][0] = s.charAt(i) == rev.charAt(0) ? 1 : 0;

for (int j = 1; j < n; j++) {

// 如果字符匹配，则在之前的基础上加 1

if (s.charAt(i) == rev.charAt(j))

f[i][j] = f[i - 1][j - 1] + 1;

// 更新最长回文子串的信息

if (f[i][j] > maxLen) {

int befPos = n - j - 1;

// 检查回文子串是否与原字符串位置相对应

if (befPos + f[i][j] - 1 == i) {

maxLen = f[i][j];

begPos = befPos;

}

}

}

}

// 返回最长回文子串

return s.substring(begPos, begPos + maxLen);

}

}

当输入字符串是 “babad” 时，我们来模拟一下整个题解过程。

• 原始字符串：s = "babad"

• 反转字符串：rev = "dabab"

我们创建一个大小为 n x n 的二维数组 f，其中 n 是字符串 s 的长度。在这个例子中，n =

5，所以 f 是一个 5x5 的表。

下面是填充表 f 的过程：

b

a

b

 a

d

• 当我们遇到匹配的字符时，例如 s[2] = b 和 rev[2] = b，我们在 f[2][2] 上设置值为

f[1][1] + 1 = 1 + 1 = 2。

• 每次我们找到一个新值，我们检查是否可以形成回文串。例如，当 f[3][3] = 3，我

们发现从 rev 的第 1 个字符到第 3 个字符的子串 aba 和原始字符串 s 中从第 1 个字符

到第 3 个字符的子串是相同的，因此我们更新最长回文串长度为 3。

可惜，虽然我们做了这么多工作，时间复杂度还是距离题目的预期有很大的差距。

005.%E6%9C%80%E9%95%BF%E5%9B%9E%E6%96%87%E5%AD%90%E4%B8%B2-

20231218143814.png

如果还不理解的话，可以通过 ACM 输入输出的模式 debug 一下。

public class Main00501 {

public static void main(String[] args) {

// 请输入字符串

System.out.println("请输入字符串：");

// 创建 Scanner 对象用于读取输入

Scanner scanner = new Scanner(System.in);

// 读取字符串

String s = scanner.nextLine();

// 创建 Solution 实例并调用 longestPalindrome 方法

Solution00501 solution = new Solution00501();

String result = solution.longestPalindrome(s);

// 输出结果

System.out.println(result);

}

}

class Solution00501 {

public String longestPalindrome(String s) {

String rev = new StringBuffer(s).reverse().toString();

int n = s.length();

 int[][] f = new int[n][n];

int maxLen = 1;

int begPos = 0;

for(int j = 0;j < n;j++)

if(rev.charAt(j) == s.charAt(0))

f[0][j] = 1;

for(int i = 1;i < n;i++){

f[i][0] = s.charAt(i) == rev.charAt(0) ? 1 : 0;

for(int j = 1;j < n;j++){

if(s.charAt(i) == rev.charAt(j))

f[i][j] = f[i - 1][j - 1] + 1;

if(f[i][j] > maxLen){

int befPos = n - j - 1;

if(befPos + f[i][j] - 1 == i) {

maxLen = f[i][j];

begPos = befPos;

}

}

}

}

return s.substring(begPos,begPos + maxLen);

}

}

除了上面这种写法，动态规划的题解还有另外一种写法：

public class Solution {

public String longestPalindrome(String s) {

int n = s.length();

boolean[][] dp = new boolean[n][n]; // 创建动态规划表

String res = ""; // 用于存储最长回文子串

for (int len = 0; len < n; len++) { // len 表示检查的子串长度

for (int start = 0; start + len < n; start++) { // start 表示子串的开始位置

int end = start + len; // end 表示子串的结束位置

// 对于长度为 1 和 2 的子串，只需比较两端字符是否相等

if (len == 0) {

dp[start][end] = true;

} else if (len == 1) {

dp[start][end] = s.charAt(start) == s.charAt(end);

} else {

// 对于长度大于 2 的子串，除了比较两端字符外，还需要检查内部子串是否为回文

dp[start][end] = (s.charAt(start) == s.charAt(end)) && dp[start + 1]

[end - 1];

}

// 更新最长回文子串

if (dp[start][end] && len + 1 > res.length()) {

res = s.substring(start, end + 1);

 }

}

}

return res;

}

}

是不是感觉更简洁了呢？

当输入字符串为 “babad” 时，我们继续来模拟整个题解过程：

仍然初始化一个 5x5 的二维数组 dp，不过是 Boolean 类型，用来表示 s 中以 start 开头和

end 结尾的子串是否是回文串。

1. 长度为 1 的子串（单个字符）：所有长度为 1 的子串（“b”, “a”, “b”, “a”, “d”）都是回

文。

2. 长度为 2 的子串：

– 检查 “ba”, “ab”, “ba”, “ad”。

– 发现都不是回文。

3. 长度为 3 的子串:

– 检查 “bab”, “aba”, “bad”。

– 发现 “bab” 和 “aba” 是回文（dp[0][2] = true 和 dp[1][3] = true），“bad” 不

是。

– res 保持为 “aba”。

4. 长度为 4 的子串:

– 检查 “baba”, “abad”。

– 发现这两个都不是回文。

5. 长度为 5 的子串:

– 检查 “babad”。

– 发现它不是回文。

球友们可以通过 ACM 的模式来调试一下代码，应该就很快能明白了。

public class Main00502 {

public static void main(String[] args) {

// 请输入字符串

System.out.println("请输入字符串：");

// 创建 Scanner 对象用于读取输入

Scanner scanner = new Scanner(System.in);

// 读取字符串

String s = scanner.nextLine();

// 创建 Solution 实例并调用 longestPalindrome 方法

Solution00502 solution = new Solution00502();

String result = solution.longestPalindrome(s);

 // 输出结果

System.out.println(result);

}

}

class Solution00502 {

public String longestPalindrome(String s) {

int n = s.length();

boolean[][] dp = new boolean[n][n]; // 创建动态规划表

String res = ""; // 用于存储最长回文子串

for (int len = 0; len < n; len++) { // len 表示检查的子串长度

for (int start = 0; start + len < n; start++) { // start 表示子串的开始位置

int end = start + len; // end 表示子串的结束位置

// 对于长度为 1 和 2 的子串，只需比较两端字符是否相等

if (len == 0) {

dp[start][end] = true;

} else if (len == 1) {

dp[start][end] = s.charAt(start) == s.charAt(end);

} else {

// 对于长度大于 2 的子串，除了比较两端字符外，还需要检查内部子串是否为回文

dp[start][end] = (s.charAt(start) == s.charAt(end)) && dp[start + 1]

[end - 1];

}

// 更新最长回文子串

if (dp[start][end] && len + 1 > res.length()) {

res = s.substring(start, end + 1);

}

}

}

return res;

}

}

但是，这种写法的时间复杂度还是 $ O(n^2) $，因为我们还是需要遍历整个二维数组。

005.%E6%9C%80%E9%95%BF%E5%9B%9E%E6%96%87%E5%AD%90%E4%B8%B2-

20231218162705.png

分析 3

原因在于我们仍然要用$ O(n^2) $的时间来遍历 i 和 j。有没有更好的办法，能让我们尽量

省去枚举 i 和 j 的遍历呢？

我们可以考虑枚举回文串的中心，然后向两边扩展。

回文可以以单个字符为中心（例如 “aba”），也可以以两个相同字符之间的空隙为中心

（例如 “abba”）。

从每个可能的中心开始，尽可能向两边扩展，当两个方向的字母不再相同时，我们就找到

了以该中心为起点的最长回文串。

public 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 = 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) {

while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {

left--; // 向左扩展

right++; // 向右扩展

 }

return right - left - 1; // 返回扩展后的回文长度

}

}

代码很好理解，唯一需要注意的是，需要两次调用 expandAroundCenter 方法，一次以

单个字符为中心，一次以两个字符之间的空隙为中心。

当输入是 “babad”时，我们来模拟一下整个题解过程。

①、以奇数长度回文串的中心扩展

对于奇数长度的回文，我们将每个字符视为中心，向两边扩展：

1. 中心 ‘b’ (第一个 ‘b’)：

– 回文子串为 “b”。

2. 中心 ‘a’ (第一个 ‘a’)：

– 回文子串可以扩展到 “bab”。

3. 中心 ‘b’ (第二个 ‘b’)：

– 回文子串可以扩展到 “aba”。

4. 中心 ‘a’ (第二个 ‘a’)：

– 回文子串为 “a”。

5. 中心 ‘d’：

– 回文子串为 “d”。

②、以偶数长度回文串的中心扩展

对于偶数长度的回文，我们将每两个相邻字符之间视为中心，向两边扩展：

1. 中心 ‘ba’ (第一个 ‘b’ 和第一个 ‘a’)：

– 无法形成回文。

2. 中心 ‘ab’ (第一个 ‘a’ 和第二个 ‘b’)：

– 无法形成回文。

3. 中心 ‘ba’ (第二个 ‘b’ 和第二个 ‘a’)：

– 无法形成回文。

4. 中心 ‘ad’ (第二个 ‘a’ 和 ‘d’)：

– 无法形成回文。

在这种情况下，我们没有找到任何偶数长度的回文子串。

好，当输入是“abbaab”时，大家可以自己模拟一下整个题解过程。

这种题解的效率也是很不错的，也容易理解。

005.%E6%9C%80%E9%95%BF%E5%9B%9E%E6%96%87%E5%AD%90%E4%B8%B2-

20231218180407.png

分析 4

这里给大家拓展一下马拉车算法（Manacher 算法）出场了。

马拉车算法 Manacher‘s Algorithm 是用来查找一个字符串的最长回文子串的线性

方法，由一个叫 Manacher 的人在 1975 年发明，这个方法的最大贡献是在于将

时间复杂度提升到了线性。

_Manacher_算法会先在每个字符之间插入一个未在字符串中出现过的字符（如#），再利

用回文半径和回文直径，依次匹配，再通过判断 i(当前位置)与 R(回文半径)的关系进行不

同的分支操作，接着继续遍历直到遍历完整个字符串。

如果对马拉车算法还比较陌生的话，可以参阅吴师兄这篇内容：https://

www.cxyxiaowu.com/2665.html

我这里帮大家梳理一下。

首先，我们需要构建一个新的字符串，其中每个原始字符之间插入特殊字符（如#），这

样做是为了统一处理奇数长度和偶数长度的回文串。

例如 “babad” 添加分隔符 “#” 以后得到 “#b#a#b#a#d#”。新字符串的回文子串一定以分隔

符作为两边的边界，因此分隔符起到“哨兵”的作用。

005.%E6%9C%80%E9%95%BF%E5%9B%9E%E6%96%87%E5%AD%90%E4%B8%B2-

20231218153146.png

接着，我们定义一个数组 p，其中 p[j]表示以字符 j 为中心的最长回文半径。

以字符串 "abbabb" 为例，说明如何手动计算得到辅助数组 p ，我们要填的就是下面这张

表。

char # a

index 0 1

p

第 1 行数组 char ：原始字符串加上分隔符以后的每个字符。

第 2 行数组 index ：这个数组是新字符串的索引数组，它的值是从 0 开始的索引编号。

我们首先填 p[0]。

以 char[0] = '#' 为中心，同时向左边向右边扩散，走 1 步就碰到左边边界了，因此能扩

散的步数为 0，因此 p[0] = 0；

char # a

index 0 1

p 0

下面填写 p[1] 。

以 char[1] = 'a' 为中心，同时向左边向右边扩散，走 1 步，左右都是 "#"，构成回文子

串，于是再继续同时向左边向右边扩散，左边碰到边界了，最多能扩散的步数”为 1，因

此 p[1] = 1；

char # a

index 0 1

p 0 1

下面填写 p[2] 。

以 char[2] = '#' 为中心，同时向左边向右边扩散，走 1 步，左边是 "a"，右边是 "b"，不

匹配，最多能扩散的步数为 0，因此 p[2] = 0；

char # a

index 0 1

p 0 1

下面填写 p[3]。

以 char[3] = 'b' 为中心，同时向左边向右边扩散，走 1 步，左右两边都是 “#”，构成回

文子串，继续同时向左边向右扩散，左边是 "a"，右边是 "b"，不匹配，最多能扩散的步

数为 1 ，因此 p[3] = 1；

char # a

index 0 1

p 0 1

下面填写 p[4]。

以 char[4] = '#' 为中心，同时向左边向右扩散，最多可以走 4 步，左边到达左边界，因

此 p[4] = 4。

char # a

index 0 1

p 0 1

继续填完 p 数组剩下的部分。

分析到这里，后面的数字不难填出，最后写成如下表格：

char # a

index 0 1

p 0 1

说明：有些资料将辅助数组 p 定义为回文半径数组，即 p[i] 记录了以新字符串第 i 个字符

为中心的回文字符串的半径（包括第 i 个字符），与我们这里定义的辅助数组 p 有一个字

符的偏差，本质上是一样的。

下面是辅助数组 p 的结论：辅助数组 p 的最大值是 5，对应了原字符串 "abbabb" 的 “最

长回文子串” ："bbabb"。这个结论具有一般性，即：

辅助数组 p 的最大值就是“最长回文子串”的长度。

简单说明一下这是为什么：

如果新回文子串的中心是一个字符，那么原始回文子串的中心也是一个字符，在新回文子

串中，向两边扩散的特点是：“先分隔符，后字符”，同样扩散的步数因为有分隔符 # 的作

用，在新字符串中每扩散两步，虽然实际上只扫到一个有效字符，但是相当于在原始字符

串中相当于计算了两个字符。

因为最后一定以分隔符结尾，还要计算一个，正好这个就可以把原始回文子串的中心算进

去；

005.%E6%9C%80%E9%95%BF%E5%9B%9E%E6%96%87%E5%AD%90%E4%B8%B2-

20231218161114.png

如果新回文子串的中心是 #，那么原始回文子串的中心就是一个“空隙”。在新回文子串

中，向两边扩散的特点是：“先字符，后分隔符”，扩散的步数因为有分隔符 # 的作用，

在新字符串中每扩散两步，虽然实际上只扫到一个有效字符，但是相当于在原始字符串中

相当于计算了两个字符。

因此，“辅助数组 p 的最大值就是“最长回文子串”的长度”这个结论是成立的，可以看下面

的图理解上面说的 2 点。

005.%E6%9C%80%E9%95%BF%E5%9B%9E%E6%96%87%E5%AD%90%E4%B8%B2-

20231218161212.png

看到这里，我估计大家已经能够明白了，来看题解：

class Solution {

// 马拉车算法实现最长回文子串

public static String longestPalindrome(String s) {

// 对空字符串或单字符字符串直接返回原字符串

if (s.length() == 0 || s.length() == 1)

return s;

// 构建一个新的字符串，其中每个原始字符之间插入特殊字符（如'#'）

// 这样做是为了统一处理奇数长度和偶数长度的回文串

StringBuilder temp = new StringBuilder("#");

for (int i = 0; i < s.length(); i++) {

temp.append(s.charAt(i)).append("#");

}

// 新字符串的长度

int n = temp.length();

// p 数组，p[j] 表示以字符 j 为中心的最长回文半径

int[] p = new int[n];

// id 是最长回文子串中心的位置，mx 是以 id 为中心的回文子串能到达的最右端的位置

int id = 0, mx = 0;

// 记录最长回文子串的长度和中心位置

int maxLength = -1;

int index = 0;

// 遍历新字符串

for (int j = 1; j < n - 1; j++) {

// 利用已知回文信息初始化 p[j]

p[j] = mx > j ? Math.min(p[2 * id - j], mx - j) : 1;

// 中心扩展，检查并更新 p[j]

while (j + p[j] < n && j - p[j] >= 0 && temp.charAt(j + p[j]) ==

temp.charAt(j - p[j])) {

p[j]++;

}

// 更新 id 和 mx

if (mx < j + p[j]) {

mx = j + p[j];

id = j;

}

// 更新最长回文子串的信息

if (maxLength < p[j] - 1) {

maxLength = p[j] - 1;

index = j;

}

}

 // 计算原始字符串中最长回文子串的起始位置

// (index - maxLength) / 2 是在添加了特殊字符的字符串中的起始位置

int start = (index - maxLength) / 2;

// 返回原始字符串中的最长回文子串

return s.substring(start, start + maxLength);

}

}

OK，搞定：

005.%E6%9C%80%E9%95%BF%E5%9B%9E%E6%96%87%E5%AD%90%E4%B8%B2-

20231218144544.png

分析 4

力扣链接：https://leetcode.cn/problems/longest-palindromic-substring/

总结

本文主要介绍了最长回文子串的四种解法，分别是：

• 暴力解法

• 动态规划

• 中心扩展法

• 马拉车算法

其中效率最高，也最容易懂的是中心扩展法，希望所有球友都能理解并掌握这种解法。主

要用到了 for 循环和 while 循环，以及字符串的 substring 方法、charAt 方法、length 方

法，推荐学习资料：

• while 循环和 for 循环

• 字符串