5. 最长回文子串(动态规划)

无优化的动态规划: 遍历1-n长度的字符串,并用dp数组记录前面的子回文串　　

时间复杂度: O(n^2)   空间复杂度: O(n^2)

 1 class Solution {
 2     public String longestPalindrome(String s) {
 3         if(s.isEmpty()) return "";
 4         int n=s.length();
 5         String res=null; //不为空肯定有一个字符为回文
 6         boolean[][] dp=new boolean[n][n]; //dp[i][j]=true:表示字符串[i,j]区段是回文
 7         for(int i=0;i<n;i++){ //单个字符默认回文
 8             dp[i][i]=true;
 9             res=s.substring(i);
10         }
11         for(int i=0;i<n-1;i++) { //判断两个字符是否回文
12             if(s.charAt(i)==s.charAt(i+1)){
13                 dp[i][i+1]=true;
14                 res=s.substring(i,i+2);
15             }
16         }
17         //print(dp,n);
18         //System.out.println();
19         for(int k=3;k<=n;k++){
20             for(int i=0;i<n+1-k;i++){
21                 if(s.charAt(i)==s.charAt(i+k-1)&&dp[i+1][i+k-2]){
22                     dp[i][i+k-1]=true;
23                     res=s.substring(i,i+k);
24                 }
25             }
26         }
27         //print(dp,n);
28         return res;
29     }
30 /*    void print(boolean[][] dp,int n) {
31         for(int i=0;i<n;i++){
32             for(int j=0;j<n;j++) System.out.print(dp[i][j]+",");
33             System.out.println();
34         }
35     }*/
36 }