《二哥的 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; // 存储最长回文子串的起始和结束