LeetCode(5)：求出s中最长的回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
           

该题可用动态规划，中心扩展，Manacher来解决

1.动态规划

思路

右指针从第二位开始，左指针在右指针的位置前面进行顺序检测是否存在回文子串，检测到满足条件就在对应的数组标记为true，若满足条件的子串长度比目前的最长长度长，就更新最长长度变量和最长的回文子串，左指针每遍历完一次，右指针就向右移动一次。

思想

对每个子问题（及子问题的子问题）只求解一次，将其解保存在一个表格中，从而在计算大规模的问题的时候，小规模的问题已经计算过，从而避免了不必要的计算工作。

复杂度

初始化二维数组时就已经把时间复杂度变成了O(n2)了（虽然这个算法本身复杂度就是O(n2)），我纳闷的是为什么java二维数组初始化时不能同时给每个值设置默认值呢，问题求解了好久也不知道该怎么设置默认值，根据我记得的基础，这是二维数组，二维数组里的对象初始化都是null，只能双重循环加入数字就很难受了。

class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        if(len <= 1) return s;
        String maxStr = s.substring(0,1);
        Boolean[][] dp = new Boolean[len][len];
        for(int i = 0; i < len; i ++)
            for(int j = 0; j < len; j ++)
                dp[i][j] = false;

        int maxlen = 1;
        for(int r = 1; r < len; r ++){
            for(int l = 0; l < r; l ++){
                if(s.charAt(l)==s.charAt(r) && (r-l<=2 || dp[l+1][r-1])){
                    dp[l][r]=true;
                    if(r-l+1 > maxlen){
                        maxlen = r-l+1;
                        maxStr = s.substring(l, r+1);
                    }
                }
            }
        }
        return maxStr;
    }
}
           

中心扩展（待更）