一. 题目

二. 思路

1. 暴力

枚举中心(单个为中心和两个为中心)，然后向两侧扩展。
O(n^2)

2. 区间DP

f[i,j]:i,j这段是不是回文串
若f[i+1, j-1]==true, 且a[i]==a[j]，则f[i,j]=true
O(n^2)

3. 二分+字符串哈希

二分最大字符串长度：二段性：若小的长度能满足，才可能更大。
使用字符串哈希O(1)判断是否为回文。
O(nlog^n)

三. 代码

2. 区间DP

class Solution
{
    static final int N = (int) 1e3 + 10;
    boolean[][] f = new boolean[N][N];

    /*
        //区间DP
        f[i,j]:i,j这段是不是回文串
        若f[i+1, j-1]==true, 且a[i]==a[j]，则f[i,j]=true
        else f[i, j]=false
     */
    public String longestPalindrome(String s)
    {
        int n = s.length();
        for (int i = 0; i < n; ++i)
            Arrays.fill(f[i], false);

        int ans = 1;
        String anss = s.substring(0, 1);
        for (int len = 1; len <= n; ++len)
            for (int l = 0; l + len - 1 < n; ++l)
                if (len == 1) f[l][l] = true;
                else if (len == 2 && s.charAt(l) == s.charAt(l + 1))
                {
                    f[l][l + 1] = true;
                    if (ans < 2)
                    {
                        ans = 2;
                        anss = s.substring(l, l + 2);
                    }
                } else if (len >= 3)
                {
                    int r = l + len - 1;
                    if (f[l + 1][r - 1] && s.charAt(l) == s.charAt(r))
                    {
                        f[l][r] = true;
                        if (ans < r - l + 1)
                        {
                            ans = r - l + 1;
                            anss = s.substring(l, l + len);
                        }
                    }
                }
        return anss;
    }
}