DP、KMP什么的都太高大上了。自己想了个朴素的遍历方法。
【题目】
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.
【思路】（应该算是O(n)吧）
从中间向两端搜索。分别找到以每一个字母为中心的最长回文子串，假设两边剩余的元素已经比当前最长回文子串的一半还短时，停止遍历。
大家别看代码长。是为了便于理解的。
【Java代码】
public class Solution {
public String longestPalindrome(String s) {
int len = s.length();
if (s == null || len == 1){
return s;
}
String ret = "";
int mid = len / 2;
int i = 0;
while (true) {
//遍历到s两端时。假设以mid+i或mid-i为中心的最长回文都不比当前最优解长，遍历结束
if (2*(len-(mid+i)) < ret.length() && 2*(mid-i+1) < ret.length()) {
break;
}
String str1 = palindrome1(s, mid+i);
String str2 = palindrome2(s, mid+i);
String str3 = palindrome1(s, mid-i);
String str4 = palindrome2(s, mid-i);
if (str1.length() > ret.length()) {
ret = str1;
}
if (str2.length() > ret.length()) {
ret = str2;
}
if (str3.length() > ret.length()) {
ret = str3;
}
if (str4.length() > ret.length()) {
ret = str4;
}
i++;
}
return ret;
}
//找出s中以index为中心的aba型的回文子串
public String palindrome1(String s, int index) {
String ret = "";
int i = index, j = index;
while (i>=0 && j<s.length()) {
if (s.charAt(i) != s.charAt(j)) {
break;
}
ret = s.substring(i, j+1);
i--;
j++;
}
return ret;
}
//找出s中以index和index+1为中心的abba型回文子串
public String palindrome2(String s, int index) {
String ret = "";
int i = index, j = index+1;
while (i>=0 && j<s.length()) {
if (s.charAt(i) != s.charAt(j)) {
break;
}
ret = s.substring(i, j+1);
i--;
j++;
}
return ret;
}
}
【分析】
后来在网上找了类似的解法。
如 http://leetcode.com/2011/11/longest-palindromic-substring-part-ii.html ，为了不用区分aba型和abba型的回文子串，构造了一个新的字符串 t ，在两端和每两个字母之间插入一个特殊字符 ‘#’ 。这样当以‘#’为中心的回文子串就是我的代码中abba型子串。
我的代码与之相比还使用了一个小trick，即从中间向两端遍历。这样假设中间已经有比較长的回文子串了，那么两端比較偏的回文子序列就可省去推断。
一遍就AC了。后来比較了网上的解法，不禁为自己有点小激动呢~。
分析可能有误，或许仅仅是自我感觉良好，欢迎大家指正！