5. Longest Palindromic Substring java solutions

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

 1 public class Solution {
 2     public String longestPalindrome(String s) {
 3         if(s == null || s.length() <= 1) return s;
 4         String ans = s.substring(0,1);
 5         for(int i = 0; i < s.length(); i++){
 6             String tmp = findPalindrome(s,i,i);//回文为奇数的情况
 7             if(tmp.length() > ans.length()) ans = tmp;
 8             
 9             tmp = findPalindrome(s,i,i+1);// 回文为偶数的情况
10             if(tmp.length() > ans.length()) ans = tmp;
11         }
12         return ans;
13     }
14     
15     public String findPalindrome(String str, int s, int e){
16         while(s >=0 && e < str.length() && str.charAt(s) == str.charAt(e)){
17             s--; e++;
18         }
19         return str.substring(++s,e);
20     }
21 }

时间复杂度O(N*(N+N+1))

本题也可以使用DP做法：

参考DP:http://blog.csdn.net/soszou/article/details/37312317