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     String longestOne = null; 3     int lengthOfLongest = 0; 4     public String longestPalindrome(String s) { 5         // Start typing your Java solution below 6         // DO NOT write main() function 7         longestOne = null; 8         lengthOfLongest = 0; 9         if(s.length() == 0){10             return longestOne;11         }12         if(s.length() == 1){13             return s;14         }15         for(int i = 0; i < s.length() - 1; i ++){16             if(s.charAt(i) == s.charAt(i+1)){17                 if((i == 0 || i == s.length() - 2) && lengthOfLongest < 2){18                         lengthOfLongest = 2;19                         longestOne = s.substring(i,i+2);20                 }21                 else{getLongestPalindrome(i - 1, i + 2, s);}22             }23         }24         for(int i = 1; i < s.length() - 1; i ++){25             getLongestPalindrome(i - 1, i + 1, s);26         }27         return longestOne;28     }29     30     public void getLongestPalindrome(int left, int right, String s){31         if(left < 0 || right >= s.length()) return;32         int j = right;33         for(int i = left; i > -1 ; i --){34             if(j < s.length() && s.charAt(i) == s.charAt(j)){35                 if(j-i+1 >= lengthOfLongest){36                     lengthOfLongest = j-i+1;37                     longestOne = s.substring(i,j+1);38                 }39             }40             else{41                 return;42             }43             j ++;44         }45     }46 }

 第二遍：

 可以将长度为奇数的substring 和 偶数substring 归并到一起。 即使用两倍长度进行循环。 如果是点 则以为中心， 如果是中间，则以两边的点为中心。 减少很多test case。

1 public class Solution { 2     public String longestPalindrome(String s) { 3         // Note: The Solution object is instantiated only once and is reused by each test case. 4         String longestOne = null; 5         int max = 0; 6         int len = s.length(); 7         for(int i = 0; i <= (len - 1)* 2; i ++){ 8             int left = (i % 2 == 1 ? i / 2 : i / 2 - 1); 9             int right = i / 2 + 1;10             while(left > -1 && right < len && s.charAt(left) == s.charAt(right)){11                 left --;12                 right ++;13             }14             if(right - left - 1 > max){15                 max = right - left - 1;16                 longestOne = s.substring(left + 1, right);17             }18         }19         return longestOne;20     }21 }

 第三遍：

1 public class Solution { 2     public String longestPalindrome(String s) { 3         if(s == null || s.length() == 0) return null; 4         int len = s.length(); 5         int max = 0; 6         int max_left = 0, max_right = 0; 7         for(int i = 0; i < len * 2 - 1; i ++){ 8             int left  = i / 2; 9             int right = (i + 1) / 2;10             while(left > -1 && right < len && s.charAt(left) == s.charAt(right)){11                 left --;12                 right ++;13             }14             if(right - left > max){15                 max = right - left;16                 max_left = left + 1;17                 max_right = right;18             }19         }20         return s.substring(max_left,max_right);21     }22 }