二哥的 LeetCode 刷题笔记：005.最长回文子串

《二哥的 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);
    }
}

但是，结果非常感人……