https://leetcode-cn.com/problems/longest-palindromic-substring/solution/

方法一：中心扩展法

遍历字符串，以每个字符为中心，判断以其为中心的最长回文串长度。记录最长回文串的起始位置。注意回文串长度分奇偶两种情况。

class Solution {
    public String longestPalindrome(String s) {
        if(s==null||s.length()<1) return s;
        //回文串左右位置
        int left=0;int right=0;
        for(int i=0;i<s.length();i++){
            //回文串长度为奇数
            int len1=lengthOfHuiwen(s,i,i);
            //长度为偶数
            int len2=lengthOfHuiwen(s,i,i+1);
            int len=Math.max(len1,len2);
            if(len>right-left){
                left=i-(len+1)/2+1;
                right=i+len/2;
            }
        }
        return s.substring(left,right+1);
    }
    //left,right为中心字符串左右位置
    public int lengthOfHuiwen(String s,int left,int right){
        int L=left,R=right;
        while(L>=0&&R<s.length()&&s.charAt(L)==s.charAt(R)){
            L--;
            R++;
        }
        return R-L-1;
    }
}

方法二：动态规划

（一）状态
    f[i][j]表示s的第 i 个字符到第 j 个字符组成的子串，是否为回文串
（二）转移方程
    如果s的第 i 个字符和第 j 个字符相同的话，且 i + 1, 到 j - 1 的子串也是回文串的话，f[i][j] 也为回文串
        f[i][j] = f[i + 1][j - 1] and s[i] == s[j]
    稍微要注意的是，如果 i == j 或者 i + 1 == j 的时候，也就是单个字符的子串和两个相邻字符的子串，就不需要f[i + 1][j - 1]了
    注意遍历顺序，i 从最后一个字符开始往前遍历，j 从 i 开始往后遍历，这样可以保证每个子问题都已经算好了。

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

}

---