Leetcode 5.最长回文子串

 1 class Solution {
 2     public String longestPalindrome(String s) {
 3        int len=s.length();
 4         if(len==0)return s;
 5         boolean dp[][]=new boolean[len][len];//dp数组表示在两个下标之间的子串是不是回文串
 6         int maxLen=0;//记录最大长度
 7          String res=null;
 8          for (int i = len-1; i >=0; i--) {//因为dp依赖与中间的dp值，所以i从尾到头遍历
 9              for (int j = i; j < len; j++) {
10                  //如果头尾两个值一样，并且头尾不是相邻时，依赖于中间dp值。
11                  //中间如果只有一个字母，那必为回文，所以判断j-1<3
12                  dp[i][j]=s.charAt(i)==s.charAt(j)&&(j-i<3||dp[i+1][j-1]);
13                  //找最长
14                  if(dp[i][j]&&(res==null||j-i>maxLen)){
15                              res=s.substring(i,j+1);//此处可优化，只记录当前最小子串左右下标，最后在取子串
16                              maxLen=j-i;
17                      }
18              }
19          }
20          return res;
21     }
22 }