leetcode 5. 最长回文子串 中等 动态规划

题目：

分析：这道题有多种思路。1.暴力法，对所有子串进行判断，如果是回文串，则判断长度是否是最长的，是则更新并记录字符串开始的索引，使用这种方法确实可行，但在leetcode是a不过的，会运行超时。
2.动态规划。动态规划怎么做，首先思考问题的最优子结构，如果一个字符串是回文串，那么它的首尾字符一定相等，并且首尾相向移动，字符也相等，如果一个字符串首尾字符相等，那么除去这两个字符的子串也是回文的话，那么这个字符串就是回文字符串，这样子问题就出现了，去除首尾两个字符，剩下的子字符串是回文的话再判断首尾字符是否相等，只有同时满足这两个条件这个字符串才是回文字符串，这样就利用到了子问题的解（是否是回文串），这里还有个问题需要注意，由于需要去掉首尾两个字符，所以长度要大于等于3才没有问题，长度为1和2的字符串需要特殊处理，否则，去掉后通过下标访问会出错（去掉后不是原问题的子问题）
上代码

class Solution {
    public String longestPalindrome(String s) {
        if(s == null || s.length() == 0){
            return "";
        }
        //记录最长回文子串开始下标
        int index = 0;
        int maxLength = 1;
        //记录下标i,j的字符串是否是回文串
        boolean[][] isReverseString = new boolean[s.length()][s.length()];
        //长度为1一定是回文串
        for(int i = 0; i < s.length(); i++){
            isReverseString[i][i] = true;
        }
        for(int i = 0; i < s.length()-1; i++){
            if(s.charAt(i) == s.charAt(i+1)){
                isReverseString[i][i+1] = true;
                index = i;
                maxLength = 2;
            }else{
                isReverseString[i][i+1] = false;
            }
        }
        for(int length = 3; length <= s.length(); length++){
            for(int i = 0; i < s.length(); i++){
                int endIndex = i + length - 1;
                if(endIndex >= s.length()){
                    break;
                }
                isReverseString[i][endIndex] = isReverseString[i+1][endIndex-1] && (s.charAt(i) == s.charAt(endIndex));
                if(isReverseString[i][endIndex] && length > maxLength){
                    maxLength  = length;
                    index = i;
                }
            }
        }
        return s.substring(index, index+maxLength);
    }
}

欢迎大家讨论及指正