试水刷题，先从简单的练起。

题目

5. 最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"
输出: "bb"

解题思路

还是老样子，构造个测试数据 s = "abccbdbccec"，然后我们先画图：

单个字符自身就是 『回文』，此处就不管了，我们只找 2 个字符以上的回文。

那首先需要检查的，就是 s[0] 和 s[1] 中间这个位置，我们就简称 s[0.5] 吧。

很显然，s[0.5] 两边的字符并不相等，那么就可以继续检查下一个位置 s[1] 了。

s[1] 两边的字符看起来也并不相等，那我们直接看个能找到回文的位置吧，s[2.5] 就不错。

s[2], s[3] 相等，不但意味着找到了第一个回文串 cc ，也意味着它两侧可能孕育着更长的回文串。

继续向两端搜索，果然看到了更长的回文串 bccb，可惜两边没有更长的了。

以此类推，对每一个位置都进行相应的查找动作。

以上的算法，需要先遍历整个字符串的位置，因为有 0.5 这种位置存在，相当于要遍历 2n 个位置。

对于每一个位置，还需要再进行一次遍历来确认是否回文，综上可得算法复杂度为 O(n²），还算可以接受。

实际写代码的时候其实还有剪枝技巧：

1. 如果当前位置，和边界的距离，已经小于已找到的最长子串，那么其实已经可以不用找了。
2. 可以合理猜测，从相对靠中间位置开始遍历，存在更大的可能性先找到最长子串，从而让第一条的剪枝更有效率。

解答

Java 代码

class Solution {
    String ans = "";

    public String longestPalindrome(String s) {
        // 居然有空字符串样例
        if (s.length() <= 1)
            return s;

        // 最惨的情况就是没有回文，相当于第一个字符自成回文
        ans = s.substring(0, 1);

        // 不严谨的实现一下从中间开始遍历
        for (int i = 0; i < s.length() / 2 + 1; i++) {
            check_pos(s, s.length() / 2 + i, true);
            check_pos(s, s.length() / 2 + i, false);
            check_pos(s, s.length() / 2 - i, true);
            check_pos(s, s.length() / 2 - i, false);
        }

        return ans;
    }

    //flag 为 true，代表查找奇数回文，pos 是中间的字符
    //flag 为 false，代表查找偶数回文，pos 是第一个字符
    public void check_pos(String s, int pos, boolean flag) {
        int skip = flag ? 1 : 0;

        if (ans.length() > Math.min(pos + 1 , s.length() - pos) * 2 + 1)
            return;

        while (true) {
            int start = pos - skip;
            int end = flag ? pos + skip : pos + skip + 1;

            // 越界就不找了
            if (start < 0 || end >= s.length())
                break;

            // 两边不同说明没戏
            if (s.charAt(start) != s.charAt(end))
                break;

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

            if (ans.length() < end - start + 1)
                ans = s.substring(start, end + 1);

            skip += 1;
        }
    }
}

显然，这份代码里还有很多边界情况可以进行优化，不过也算凑合着能跑，毕竟是 O(n²）的算法，不能要求太高。

那么有没有 O(n）的算法呢？
那就需要了解一下 Manacher 算法了，可以看下一篇文章。