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

示例 1：

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

方法一：

 1     /*
 2      * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
 3      * 示例 1：
 4         输入: "babad"
 5         输出: "bab"
 6         注意: "aba" 也是一个有效答案
 7      */
 8     public String longestPalindrome2(String s) {
 9         if(s == null) {
10             throw new IllegalArgumentException("参数输入错误");
11         }
12         if(s.length() <= 1) {
13             return s;
14         }
15         /*//该段代码可省略    
16          if(s.length() == 2) {
17             if(s.charAt(0) == s.charAt(1)) {
18                 return s;
19             }else {
20                 return s.substring(0,1);
21             }
22         }*/
23         int len = s.length();
24         int start = 0;
25         int end = 0;
26         boolean[][] palimdrome = new boolean[len][len];
27         //边界条件：1单个字符都为回文子串，2相邻的两个字符相同则为回文子串
28         for(int i=0; i<len; i++) {
29             palimdrome[i][i] = true;
30             if(i<len-1) {
31                 if(s.charAt(i) == s.charAt(i+1)) {
32                     palimdrome[i][i+1] = true;
33                     start = i;
34                     end = i + 1;
35                 }else {
36                     palimdrome[i][i+1] = false;
37                 }                
38             }
39         }
40         //最优子结构：根据对于字符串str，假设dp[i,j]=true表示str[i...j]是回文子串，那个必定存在dp[i+1,j-1]=true
41         //可以得到最优子结构
42         for(int l=2; l<len; l++) {  //依次判断不同长度的子字符串是否是回文字符，长度从l+1=3(l=2)开始，4、5...
43             for(int i=0; i<len-l; i++){  //首字符位置不断右移
44                 int j = i + l;
45                 if(s.charAt(i) == s.charAt(j)) {
46                     palimdrome[i][j] = palimdrome[i+1][j-1];
47                     if(palimdrome[i][j]) {
48                         if((l) > (end - start)) {
49                             start = i;
50                             end = j;
51                         }
52                     }
53                 }else {
54                     palimdrome[i][j] = false;
55                 }
56             }
57         }
58         return s.substring(start, end + 1);
59     }

推荐阅读：https://www.cnblogs.com/mini-coconut/p/9074315.html