Longest Palindromic Substring

DP方法

 // Longest Palindromic Substring  
 // Dynamic Programming  
 // boolean table[i][j] means the substring from ith char to jth char is Palindrome or not  
 public class Solution {  
   public String longestPalindromicSubstring(String s) {  
     if (s == null || s.isEmpty())  
       return "";  
     int len = s.length();  
     boolean[][] table = new boolean[len][len];  
     for (int i=0; i<len; i++) {  
       table[i][i] = true;  
     }  
     for (int i=0; i<len-1; i++) {  
       if (s.charAt(i) == s.charAt(i+1))  
         table[i][i+1] = true;  
     }  
     for (int l=3; l<=len; l++) {  
       for (int i=0; i<=len-l; i++) {  
         int j=i+l-1;  
         if (s.charAt(i) == s.charAt(j)){  
           table[i][j] = table[i+1][j-1];  
         }  
       }  
     }  
     String ans = new String();  
     for (int i=0; i<len; i++) {  
       for (int j=i; j<len; j++) {  
         if (table[i][j]) {  
           if (ans.length() < j-i+1) {  
             ans = s.substring(i, j+1);  
           }  
         }  
       }  
     }  
     return ans;  
   }  
 }  

非DP方法

 public static String longestPalindrome(String s) {  
     if (s == null || s.length() < 2)  
       return s;  
     int len = s.length();  
     String ans = new String();  
     for (int i=0; i<len-1; i++) {  
       String a = getPalindrome(s, i, i);  
       String b = getPalindrome(s, i, i+1);  
       if (ans.length() < a.length())  
            ans = a;  
       if (ans.length() < b.length())  
            ans = b;  
     }  
     return ans;  
   }  
   public static String getPalindrome(String s, int start, int end) {  
     if (s == null || s.length() == 0)  
       return "";  
     if (start > end)  
       return "";  
     while (start >= 0 && end < s.length()) {  
       if (s.charAt(start) != s.charAt(end))  
         break;  
       else {  
         start--;  
         end++;  
       }  
     }  
     return s.substring(start+1, end);  
   }