【方法1】动态规划【时间复杂度 O(n^2) 空间复杂度 O(n^2)】

发现规律：某事物符合某一条件且该事物的子集也符合这一条件时，可以考虑dp，即动态规划

对于一个子串而言，如果它是回文串，并且长度大于 2，那么将它首尾的两个字母去除之后，它仍然是个回文串。

状态转移方程：只有 s[i+1:j-1] 是回文串，并且第 i 和 j 个字母相同时，s[i:j] 才会是回文串。

代码思路：外循环当前寻找回文串的长度，表示为 l +1。l 初始化为0是因为可能就没有回文串

这个方法还是很好理解的

class Solution {    public String longestPalindrome(String s) {        int n = s.length();        boolean[][] dp = new boolean[n][n];        String ans = "";        for (int l = 0; l < n; ++l) {            for (int i = 0; i + l < n; ++i) {                int j = i + l;                if (l == 0) {                    dp[i][j] = true;                } else if (l == 1) {                    dp[i][j] = (s.charAt(i) == s.charAt(j));                } else {                    dp[i][j] = (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1]);                }                if (dp[i][j] && l + 1 > ans.length()) {                    ans = s.substring(i, i + l + 1);                }            }        }        return ans;    }}

【方法2】中心扩展【时间复杂度 O(n^2) 空间复杂度 O(n^2)】

与动态规划相反，这个方法是从里到外判断两侧字母是否相等

循环主串的每一个位置，以当前位置为中心进行扩展（注意回文串长度会有单双的情况），然后选取最长回文串

【方法3】Manacher 算法【时间复杂度 O(n) 空间复杂度 O(n)】

十分复杂，直接告辞