题目

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

示例 1：

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

示例 2：

输入: "cbbd" 输出: "bb"

分析

初始状态：

dp[i][i]=1;//单个字符是回文串dp[i][i+1]=1 if s[i]=s[i+1];//连续两个相同字符是回文串

为了改进暴力法，我们首先观察如何避免在验证回文时进行不必要的重复计算。考虑 “ababa” 这个示例。如果我们已经知道“bab” 是回文，那么很明显，“ababa”一定是回文，因为它的左首字母和右尾字母是相同的。

我们给出 P(i,j)P(i,j) 的定义如下：

因此，

基本示例如下：

这产生了一个直观的动态规划解法，我们首先初始化一字母和二字母的回文，然后找到所有三字母回文，并依此类推…

复杂度分析

时间复杂度：O(n^2)O(n2)，这里给出我们的运行时间复杂度为 O(n^2)。

空间复杂度：O(n^2)O(n2)，该方法使用 O(n^2)的空间来存储表。

代码 

public String longestPalindrome(String s) { int len = s.length(); if(len == 0 || len == 1) return s; int[][] dp = new int[len][len]; //定义二位数组存储值，dp值为1表示true，为0表示false int start = 0; //回文串的开始位置 int max = 1; //回文串的最大长度 for(int i = 0; i < len; i++){ //初始化状态 dp[i][i] = 1; if(i < len - 1 && s.charAt(i) == s.charAt(i+1)){ dp[i][i+1] = 1; start = i; max = 2; } } for(int l = 3; l <= len; l++){ //l表示检索的子串长度，等于3表示先检索长度为3的子串 for (int i = 0; i+l-1 < len; i++){ int j = l+i-1; //终止字符位置 if(s.charAt(i) == s.charAt(j) && dp[i+1][j-1] == 1){ //状态转移 dp[i][j] = 1; //是一，不是字母l start = i; max = l; } } } return s.substring(start,start + max); //获取最长回文子串 }