最长回文子串

题目描述：给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。回文是一个正读和反读都相同的字符串。

示例：输入: "babad" 输出: "bab"

Java代码：

class Solution {
    //动态规划
    public String longestPalindrome(String s) {
        int n = s.length();
        if(n < 2) return s;
        if(n == 0 || s == null) return "";
        int max = 1, begin = 0;

        //matrix[i][j]表示s[i][j]是否是回文子串
        boolean[][] matrix = new boolean[n][n];
        char[] s_new = s.toCharArray(); //转换为数组可以避免使用s.charAt(i)操作增加算法运行时间

        for(int i = 0;i < n;i++) matrix[i][i] = true; //对角线元素也就是子串长度为1时，一定是回文子串
        for(int j = 1;j < n;j++) {
            for(int i = 0;i < j;i++) {
                //matrix[i][j] = s_new[i] == s_new[j] && (j - i < 3 || matrix[i + 1][j - 1])
                //下面的逻辑可以简化为上面这一句话，但是没有铺垫不好理解
                if(s_new[i] != s_new[j]) matrix[i][j] = false;
                else {
                    if(j - i < 3) matrix[i][j] = true;
                    else matrix[i][j] = matrix[i + 1][j - 1];
                }

                //当matrix[i][j]为true时，就表示s[i...j]是回文子串，此时记录子串长度和起始位置
                if(matrix[i][j] && j - i + 1 > max) {
                    max = j - i + 1;
                    begin = i;
                }
            }
        }

        return s.substring(begin, begin + max);
    }


    //暴力解法，时间复杂度为n的三次方
    public String longestPalindrome2(String s) {
        if(s == null || s.length() == 0) return "";
        int n = s.length();
        String max = "";
        for(int i = 0;i < n;i++) {
            for(int j = i;j < n;j++) {
                if(isPalindrome(s.substring(i, j + 1)) && j - i + 1 > max.length())
                    max = s.substring(i, j + 1);
            }
        }

        return max;
    }

    public boolean isPalindrome(String s) {
        String d = new StringBuilder(s).reverse().toString();
        return s.equals(d);
    }
}