20559 字
约 68 分钟
1
005.最长回文子串
2026-09-19
数据结构与算法
无标签

005.最长回文子串

作者：沉默王二 发布时间：2023-12-18T19:04:10.495+0800

  • 语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu

  • 技术派专栏地址：https://paicoding.com/column/7/5

  • 星球原地址：https://t.zsxq.com/15M14K6ls

  • 增加代码注释，这样大家更容易看懂并掌握题解；

  • 增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；

  • 增加手绘图，这样大家更容易理解解题思路；

  • 增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；

  • 增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；

  • 图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。

  • 另外，这一版本会作为 PDF 的终稿随后在星球进行发布。

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

------------------------by鲁迅

题意

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

示例

输入：s="babad"

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

难度

中等

分析 1

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

  • 什么是字符串的反序？
  • 什么是回文串？
  • 什么是最长回文子串？

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

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

最后，最长回文子串就是在一个字符串中，最长的回文串，例如：abcba的最长回文子串就是abcba，而示例中的babad的最长回文子串就是bab或者aba。

那搞清楚这几个概念后，我们就很容易想到暴力解法：截取每一段子串，然后判断它是不是回文串，如果是的话，就更新最长回文子串。

class Solution {

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);    }}

但是，结果非常感人……

完全无法接受的结果，两层循环 的时间复杂度，再加上判断回文串又是 的时间复杂度，所以总共是 的时间复杂度，这完完全全超出了题目预期的范围。

分析 2

我们来想想其他的方法。

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

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

是的，见下图。

但是有一个问题。

例如：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 {

    // 反转原始字符串        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 的过程：

  • 当我们遇到匹配的字符时，例如 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。

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

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

public class Main00501 {

    // 请输入字符串        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 {

    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 的子串（"b", "a", "b", "a", "d"）都是回文。
  • 长度为 2 的子串：
  • 检查 "ba", "ab", "ba", "ad"。
  • 发现都不是回文。
  • 长度为 3 的子串:
  • 检查 "bab", "aba", "bad"。
  • 发现 "bab" 和 "aba" 是回文（dp[0][2] = true 和 dp[1][3] = true），"bad" 不是。
  • res 保持为 "aba"。
  • 长度为 4 的子串:
  • 检查 "baba", "abad"。
  • 发现这两个都不是回文。
  • 长度为 5 的子串:
  • 检查 "babad"。
  • 发现它不是回文。

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

public class Main00502 {

    // 请输入字符串        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; }}

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

分析 3

原因在于我们仍然要用的时间来遍历i和j。有没有更好的办法，能让我们尽量省去枚举i和j的遍历呢？

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

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

从每个可能的中心开始，尽可能向两边扩展，当两个方向的字母不再相同时，我们就找到了以该中心为起点的最长回文串。

public class Solution {

    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"时，我们来模拟一下整个题解过程。

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

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

  • 中心 'b' (第一个 'b')：
  • 回文子串为 "b"
  • 中心 'a' (第一个 'a')：
  • 回文子串可以扩展到 "bab"。
  • 中心 'b' (第二个 'b')：
  • 回文子串可以扩展到 "aba"。
  • 中心 'a' (第二个 'a')：
  • 回文子串为 "a"。
  • 中心 'd'：
  • 回文子串为 "d"。

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

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

  • 中心 'ba' (第一个 'b' 和第一个 'a')：
  • 无法形成回文。
  • 中心 'ab' (第一个 'a' 和第二个 'b')：
  • 无法形成回文。
  • 中心 'ba' (第二个 'b' 和第二个 'a')：
  • 无法形成回文。
  • 中心 'ad' (第二个 'a' 和 'd')：
  • 无法形成回文。

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

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

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

分析 4

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

马拉车算法 Manacher‘s Algorithm 是用来查找一个字符串的最长回文子串的线性方法，由一个叫 Manacher 的人在1975年发明，这个方法的最大贡献是在于将时间复杂度提升到了线性。

Manacher算法会先在每个字符之间插入一个未在字符串中出现过的字符（如#），再利用回文半径和回文直径，依次匹配，再通过判断i(当前位置)与R(回文半径)的关系进行不同的分支操作，接着继续遍历直到遍历完整个字符串。

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

我这里帮大家梳理一下。

首先，我们需要构建一个新的字符串，其中每个原始字符之间插入特殊字符（如#），这样做是为了统一处理奇数长度和偶数长度的回文串。

例如 "babad" 添加分隔符 "#" 以后得到 "#b#a#b#a#d#"。新字符串的回文子串一定以分隔符作为两边的边界，因此分隔符起到“哨兵”的作用。

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

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

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

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

我们首先填 p[0]。

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

下面填写 p[1] 。

以 char[1] = 'a' 为中心，同时向左边向右边扩散，走 1 步，左右都是 "#"，构成回文子串，于是再继续同时向左边向右边扩散，左边碰到边界了，最多能扩散的步数”为 1，因此 p[1] = 1；

下面填写 p[2] 。

以 char[2] = '#' 为中心，同时向左边向右边扩散，走 1 步，左边是 "a"，右边是 "b"，不匹配，最多能扩散的步数为 0，因此 p[2] = 0；

下面填写 p[3]。

以 char[3] = 'b' 为中心，同时向左边向右边扩散，走 1 步，左右两边都是 “#”，构成回文子串，继续同时向左边向右扩散，左边是 "a"，右边是 "b"，不匹配，最多能扩散的步数为 1 ，因此 p[3] = 1；

下面填写 p[4]。

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

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

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

说明：有些资料将辅助数组 p 定义为回文半径数组，即 p[i] 记录了以新字符串第 i 个字符为中心的回文字符串的半径（包括第 i 个字符），与我们这里定义的辅助数组 p 有一个字符的偏差，本质上是一样的。

下面是辅助数组 p 的结论：辅助数组 p 的最大值是 5，对应了原字符串 "abbabb" 的 “最长回文子串” ："bbabb"。这个结论具有一般性，即：

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

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

如果新回文子串的中心是一个字符，那么原始回文子串的中心也是一个字符，在新回文子串中，向两边扩散的特点是：“先分隔符，后字符”，同样扩散的步数因为有分隔符 # 的作用，在新字符串中每扩散两步，虽然实际上只扫到一个有效字符，但是相当于在原始字符串中相当于计算了两个字符。

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

如果新回文子串的中心是 #，那么原始回文子串的中心就是一个“空隙”。在新回文子串中，向两边扩散的特点是：“先字符，后分隔符”，扩散的步数因为有分隔符 # 的作用，在新字符串中每扩散两步，虽然实际上只扫到一个有效字符，但是相当于在原始字符串中相当于计算了两个字符。

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

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

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，搞定：

分析 4

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

总结

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

  • 暴力解法
  • 动态规划
  • 中心扩展法
  • 马拉车算法

其中效率最高，也最容易懂的是中心扩展法，希望所有球友都能理解并掌握这种解法。主要用到了 for 循环和 while 循环，以及字符串的 substring 方法、charAt 方法、length 方法，推荐学习资料：

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

该题解目前只针对**二哥编程星球 **的球友开放，如果你也想一起打卡学习算法的话，扫下面的优惠券加入我们吧，星球目前 4100+ 人，定价 149 元，从当初的 99 元一路涨上来的，所以早就是优势，别再犹豫了。

（优惠券仅 300 张，数量有限）

一个人可以走得很快，但一群人才能走得更远。如果想去面中大厂的话，LeetCode 几乎是必刷的，二哥的 LeetCode 题解通俗易懂、图文并茂，理解给你举一反三的解题能力，冲鸭。

    - 语雀专栏地址+密码可通过星球置顶帖查看：[https://t.zsxq.com/15rEo9Pdu](https://t.zsxq.com/15rEo9Pdu)

  • 技术派专栏地址：https://paicoding.com/column/7/5

  • 星球原地址：https://t.zsxq.com/15M14K6ls

  • 增加代码注释，这样大家更容易看懂并掌握题解；

  • 增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；

  • 增加手绘图，这样大家更容易理解解题思路；

  • 增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；

  • 增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；

  • 图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。

  • 另外，这一版本会作为 PDF 的终稿随后在星球进行发布。

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

------------------------by鲁迅

题意

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

示例

输入：s="babad"

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

难度

中等

分析 1

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

  • 什么是字符串的反序？
  • 什么是回文串？
  • 什么是最长回文子串？

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

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

最后，最长回文子串就是在一个字符串中，最长的回文串，例如：abcba的最长回文子串就是abcba，而示例中的babad的最长回文子串就是bab或者aba。

那搞清楚这几个概念后，我们就很容易想到暴力解法：截取每一段子串，然后判断它是不是回文串，如果是的话，就更新最长回文子串。

class Solution {

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);    }}

但是，结果非常感人……

完全无法接受的结果，两层循环 的时间复杂度，再加上判断回文串又是 的时间复杂度，所以总共是 的时间复杂度，这完完全全超出了题目预期的范围。

分析 2

我们来想想其他的方法。

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

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

是的，见下图。

但是有一个问题。

例如：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 {

    // 反转原始字符串        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 的过程：

  • 当我们遇到匹配的字符时，例如 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。

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

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

public class Main00501 {

    // 请输入字符串        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 {

    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 的子串（"b", "a", "b", "a", "d"）都是回文。
  • 长度为 2 的子串：
  • 检查 "ba", "ab", "ba", "ad"。
  • 发现都不是回文。
  • 长度为 3 的子串:
  • 检查 "bab", "aba", "bad"。
  • 发现 "bab" 和 "aba" 是回文（dp[0][2] = true 和 dp[1][3] = true），"bad" 不是。
  • res 保持为 "aba"。
  • 长度为 4 的子串:
  • 检查 "baba", "abad"。
  • 发现这两个都不是回文。
  • 长度为 5 的子串:
  • 检查 "babad"。
  • 发现它不是回文。

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

public class Main00502 {

    // 请输入字符串        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; }}

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

分析 3

原因在于我们仍然要用的时间来遍历i和j。有没有更好的办法，能让我们尽量省去枚举i和j的遍历呢？

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

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

从每个可能的中心开始，尽可能向两边扩展，当两个方向的字母不再相同时，我们就找到了以该中心为起点的最长回文串。

public class Solution {

    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"时，我们来模拟一下整个题解过程。

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

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

  • 中心 'b' (第一个 'b')：
  • 回文子串为 "b"
  • 中心 'a' (第一个 'a')：
  • 回文子串可以扩展到 "bab"。
  • 中心 'b' (第二个 'b')：
  • 回文子串可以扩展到 "aba"。
  • 中心 'a' (第二个 'a')：
  • 回文子串为 "a"。
  • 中心 'd'：
  • 回文子串为 "d"。

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

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

  • 中心 'ba' (第一个 'b' 和第一个 'a')：
  • 无法形成回文。
  • 中心 'ab' (第一个 'a' 和第二个 'b')：
  • 无法形成回文。
  • 中心 'ba' (第二个 'b' 和第二个 'a')：
  • 无法形成回文。
  • 中心 'ad' (第二个 'a' 和 'd')：
  • 无法形成回文。

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

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

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

分析 4

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

马拉车算法 Manacher‘s Algorithm 是用来查找一个字符串的最长回文子串的线性方法，由一个叫 Manacher 的人在1975年发明，这个方法的最大贡献是在于将时间复杂度提升到了线性。

Manacher算法会先在每个字符之间插入一个未在字符串中出现过的字符（如#），再利用回文半径和回文直径，依次匹配，再通过判断i(当前位置)与R(回文半径)的关系进行不同的分支操作，接着继续遍历直到遍历完整个字符串。

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

我这里帮大家梳理一下。

首先，我们需要构建一个新的字符串，其中每个原始字符之间插入特殊字符（如#），这样做是为了统一处理奇数长度和偶数长度的回文串。

例如 "babad" 添加分隔符 "#" 以后得到 "#b#a#b#a#d#"。新字符串的回文子串一定以分隔符作为两边的边界，因此分隔符起到“哨兵”的作用。

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

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

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

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

我们首先填 p[0]。

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

下面填写 p[1] 。

以 char[1] = 'a' 为中心，同时向左边向右边扩散，走 1 步，左右都是 "#"，构成回文子串，于是再继续同时向左边向右边扩散，左边碰到边界了，最多能扩散的步数”为 1，因此 p[1] = 1；

下面填写 p[2] 。

以 char[2] = '#' 为中心，同时向左边向右边扩散，走 1 步，左边是 "a"，右边是 "b"，不匹配，最多能扩散的步数为 0，因此 p[2] = 0；

下面填写 p[3]。

以 char[3] = 'b' 为中心，同时向左边向右边扩散，走 1 步，左右两边都是 “#”，构成回文子串，继续同时向左边向右扩散，左边是 "a"，右边是 "b"，不匹配，最多能扩散的步数为 1 ，因此 p[3] = 1；

下面填写 p[4]。

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

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

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

说明：有些资料将辅助数组 p 定义为回文半径数组，即 p[i] 记录了以新字符串第 i 个字符为中心的回文字符串的半径（包括第 i 个字符），与我们这里定义的辅助数组 p 有一个字符的偏差，本质上是一样的。

下面是辅助数组 p 的结论：辅助数组 p 的最大值是 5，对应了原字符串 "abbabb" 的 “最长回文子串” ："bbabb"。这个结论具有一般性，即：

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

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

如果新回文子串的中心是一个字符，那么原始回文子串的中心也是一个字符，在新回文子串中，向两边扩散的特点是：“先分隔符，后字符”，同样扩散的步数因为有分隔符 # 的作用，在新字符串中每扩散两步，虽然实际上只扫到一个有效字符，但是相当于在原始字符串中相当于计算了两个字符。

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

如果新回文子串的中心是 #，那么原始回文子串的中心就是一个“空隙”。在新回文子串中，向两边扩散的特点是：“先字符，后分隔符”，扩散的步数因为有分隔符 # 的作用，在新字符串中每扩散两步，虽然实际上只扫到一个有效字符，但是相当于在原始字符串中相当于计算了两个字符。

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

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

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，搞定：

分析 4

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

总结

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

  • 暴力解法
  • 动态规划
  • 中心扩展法
  • 马拉车算法

其中效率最高，也最容易懂的是中心扩展法，希望所有球友都能理解并掌握这种解法。主要用到了 for 循环和 while 循环，以及字符串的 substring 方法、charAt 方法、length 方法，推荐学习资料：

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

该题解目前只针对**二哥编程星球 **的球友开放，如果你也想一起打卡学习算法的话，扫下面的优惠券加入我们吧，星球目前 4100+ 人，定价 149 元，从当初的 99 元一路涨上来的，所以早就是优势，别再犹豫了。

（优惠券仅 300 张，数量有限）

一个人可以走得很快，但一群人才能走得更远。如果想去面中大厂的话，LeetCode 几乎是必刷的，二哥的 LeetCode 题解通俗易懂、图文并茂，理解给你举一反三的解题能力，冲鸭。

    - 语雀专栏地址+密码可通过星球置顶帖查看：[https://t.zsxq.com/15rEo9Pdu](https://t.zsxq.com/15rEo9Pdu)

  • 技术派专栏地址：https://paicoding.com/column/7/5

  • 星球原地址：https://t.zsxq.com/15M14K6ls

  • 增加代码注释，这样大家更容易看懂并掌握题解；

  • 增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；

  • 增加手绘图，这样大家更容易理解解题思路；

  • 增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；

  • 增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；

  • 图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。

  • 另外，这一版本会作为 PDF 的终稿随后在星球进行发布。

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

------------------------by鲁迅

题意

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

示例

输入：s="babad"

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

难度

中等

分析 1

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

  • 什么是字符串的反序？
  • 什么是回文串？
  • 什么是最长回文子串？

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

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

最后，最长回文子串就是在一个字符串中，最长的回文串，例如：abcba的最长回文子串就是abcba，而示例中的babad的最长回文子串就是bab或者aba。

那搞清楚这几个概念后，我们就很容易想到暴力解法：截取每一段子串，然后判断它是不是回文串，如果是的话，就更新最长回文子串。

class Solution {

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);    }}

但是，结果非常感人……

完全无法接受的结果，两层循环 的时间复杂度，再加上判断回文串又是 的时间复杂度，所以总共是 的时间复杂度，这完完全全超出了题目预期的范围。

分析 2

我们来想想其他的方法。

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

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

是的，见下图。

但是有一个问题。

例如：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 {

    // 反转原始字符串        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 的过程：

  • 当我们遇到匹配的字符时，例如 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。

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

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

public class Main00501 {

    // 请输入字符串        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 {

    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 的子串（"b", "a", "b", "a", "d"）都是回文。
  • 长度为 2 的子串：
  • 检查 "ba", "ab", "ba", "ad"。
  • 发现都不是回文。
  • 长度为 3 的子串:
  • 检查 "bab", "aba", "bad"。
  • 发现 "bab" 和 "aba" 是回文（dp[0][2] = true 和 dp[1][3] = true），"bad" 不是。
  • res 保持为 "aba"。
  • 长度为 4 的子串:
  • 检查 "baba", "abad"。
  • 发现这两个都不是回文。
  • 长度为 5 的子串:
  • 检查 "babad"。
  • 发现它不是回文。

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

public class Main00502 {

    // 请输入字符串        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; }}

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

分析 3

原因在于我们仍然要用的时间来遍历i和j。有没有更好的办法，能让我们尽量省去枚举i和j的遍历呢？

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

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

从每个可能的中心开始，尽可能向两边扩展，当两个方向的字母不再相同时，我们就找到了以该中心为起点的最长回文串。

public class Solution {

    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"时，我们来模拟一下整个题解过程。

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

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

  • 中心 'b' (第一个 'b')：
  • 回文子串为 "b"
  • 中心 'a' (第一个 'a')：
  • 回文子串可以扩展到 "bab"。
  • 中心 'b' (第二个 'b')：
  • 回文子串可以扩展到 "aba"。
  • 中心 'a' (第二个 'a')：
  • 回文子串为 "a"。
  • 中心 'd'：
  • 回文子串为 "d"。

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

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

  • 中心 'ba' (第一个 'b' 和第一个 'a')：
  • 无法形成回文。
  • 中心 'ab' (第一个 'a' 和第二个 'b')：
  • 无法形成回文。
  • 中心 'ba' (第二个 'b' 和第二个 'a')：
  • 无法形成回文。
  • 中心 'ad' (第二个 'a' 和 'd')：
  • 无法形成回文。

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

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

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

分析 4

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

马拉车算法 Manacher‘s Algorithm 是用来查找一个字符串的最长回文子串的线性方法，由一个叫 Manacher 的人在1975年发明，这个方法的最大贡献是在于将时间复杂度提升到了线性。

Manacher算法会先在每个字符之间插入一个未在字符串中出现过的字符（如#），再利用回文半径和回文直径，依次匹配，再通过判断i(当前位置)与R(回文半径)的关系进行不同的分支操作，接着继续遍历直到遍历完整个字符串。

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

我这里帮大家梳理一下。

首先，我们需要构建一个新的字符串，其中每个原始字符之间插入特殊字符（如#），这样做是为了统一处理奇数长度和偶数长度的回文串。

例如 "babad" 添加分隔符 "#" 以后得到 "#b#a#b#a#d#"。新字符串的回文子串一定以分隔符作为两边的边界，因此分隔符起到“哨兵”的作用。

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

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

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

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

我们首先填 p[0]。

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

下面填写 p[1] 。

以 char[1] = 'a' 为中心，同时向左边向右边扩散，走 1 步，左右都是 "#"，构成回文子串，于是再继续同时向左边向右边扩散，左边碰到边界了，最多能扩散的步数”为 1，因此 p[1] = 1；

下面填写 p[2] 。

以 char[2] = '#' 为中心，同时向左边向右边扩散，走 1 步，左边是 "a"，右边是 "b"，不匹配，最多能扩散的步数为 0，因此 p[2] = 0；

下面填写 p[3]。

以 char[3] = 'b' 为中心，同时向左边向右边扩散，走 1 步，左右两边都是 “#”，构成回文子串，继续同时向左边向右扩散，左边是 "a"，右边是 "b"，不匹配，最多能扩散的步数为 1 ，因此 p[3] = 1；

下面填写 p[4]。

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

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

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

说明：有些资料将辅助数组 p 定义为回文半径数组，即 p[i] 记录了以新字符串第 i 个字符为中心的回文字符串的半径（包括第 i 个字符），与我们这里定义的辅助数组 p 有一个字符的偏差，本质上是一样的。

下面是辅助数组 p 的结论：辅助数组 p 的最大值是 5，对应了原字符串 "abbabb" 的 “最长回文子串” ："bbabb"。这个结论具有一般性，即：

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

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

如果新回文子串的中心是一个字符，那么原始回文子串的中心也是一个字符，在新回文子串中，向两边扩散的特点是：“先分隔符，后字符”，同样扩散的步数因为有分隔符 # 的作用，在新字符串中每扩散两步，虽然实际上只扫到一个有效字符，但是相当于在原始字符串中相当于计算了两个字符。

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

如果新回文子串的中心是 #，那么原始回文子串的中心就是一个“空隙”。在新回文子串中，向两边扩散的特点是：“先字符，后分隔符”，扩散的步数因为有分隔符 # 的作用，在新字符串中每扩散两步，虽然实际上只扫到一个有效字符，但是相当于在原始字符串中相当于计算了两个字符。

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

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

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，搞定：

分析 4

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

总结

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

  • 暴力解法
  • 动态规划
  • 中心扩展法
  • 马拉车算法

其中效率最高，也最容易懂的是中心扩展法，希望所有球友都能理解并掌握这种解法。主要用到了 for 循环和 while 循环，以及字符串的 substring 方法、charAt 方法、length 方法，推荐学习资料：

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

该题解目前只针对**二哥编程星球 **的球友开放，如果你也想一起打卡学习算法的话，扫下面的优惠券加入我们吧，星球目前 4100+ 人，定价 149 元，从当初的 99 元一路涨上来的，所以早就是优势，别再犹豫了。

（优惠券仅 300 张，数量有限）

一个人可以走得很快，但一群人才能走得更远。如果想去面中大厂的话，LeetCode 几乎是必刷的，二哥的 LeetCode 题解通俗易懂、图文并茂，理解给你举一反三的解题能力，冲鸭。

            知识星球
            
    
    
        
        扫码加入星球
        查看更多优质内容
    
    https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412
005.最长回文子串
http://www.clxhxhhr.top/posts/2430/
作者
clxstart
发布于
2026-09-19
许可协议
CC BY-NC-SA 4.0
004.寻找两个正序数组的中位数
006.Z 字形变换
评论
0 条
还没有评论，先写一条吧。
☰ 文章目录