1、前言

这题目的思路就是双指针从某一个点，向两边扩展，还需要考虑奇偶情况。

题目描述

2、思路

采用中心向两边扩展的方法。答题模版如下：

for 0 <= i < len(s):
    找到以 s[i] 为中心的回文串
    找到以 s[i] 和 s[i+1] 为中心的回文串
    更新答案

此题还可以使用动态规划的方法来做，定义 dp[j][i] 为 j 到 i 是否是回文串，如果 s[j] == s[i] 时，dp[j + 1][i - 1] 也是回文串，那么字符串从 j 到 i 是回文串，即 dp[j][i] = true。

3、代码

public class LongestPalindrome {

    /**
     * 中心向两边扩展
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
        String res = "";
        for(int i = 0; i < s.length(); i++){
            String s1 = palindRom(s, i, i);
            String s2 = palindRom(s, i, i + 1);

            String str = s1.length() > s2.length() ? s1 : s2;
            res = res.length() > str.length() ? res : str;
        }

        return res;
    }

    private String palindRom(String s, int l, int r) {
        while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)){
            l--;
            r++;
        }
        return s.substring(l + 1, r);
    }


    /**
     * 动态规划
     * @param s
     * @return
     */
    public String longestPalindrome2(String s) {
        int m = s.length();
        boolean[][] dp = new boolean[m][m];
        String res = "";
        for(int i = 0; i < m; i++){
            for(int j = 0; j <= i; j++){
                if(s.charAt(j) == s.charAt(i) && (i - j < 2 || dp[j + 1][i - 1])){
                    dp[j][i] = true;
                    if(dp[j][i] && i - j + 1 > res.length()){
                        res = s.substring(j, i + 1);
                    }
                }
            }
        }

        return res;
    }

    public static void main(String[] args) {
        String s = "babad";
        System.out.println(new LongestPalindrome().longestPalindrome2(s));
    }
}