java最大回文字符串长度_Leet Code 5 最长回文子串 - Java
给定字符串S，求它的最长回文子串。你可以假设S的最大长度为1000，并且仅有唯一的最长回文子串。
第一种方法：
从左到右扫描字符串S，对每个字符查找后面与该字符相同的字符，判断以这两个相同字符为首尾的字符串是否是回文，如果是到目前为止发现的最长回文子串，则记录该子串的起始结束位置。
Leet Code测试耗时 101ms。性能太差，还需优化。
public class Solution {
public static String longestPalindrome(String s) {
if (s == null || s.length() <= 1) {
return s;
}
int longestStart = 0;
int longestEnd = 0;
for (int i = 0; i < s.length() - 1; i++) {
int end = -1;
while ((end = s.indexOf(s.charAt(i),
Math.max(longestEnd + 1, Math.max(i + 1, end + 1)))) != -1) {
if (end - i > longestEnd - longestStart) {
if (isPalindrome(s, i, end)) {
longestStart = i;
longestEnd = end;
}
}
}
if (longestEnd == s.length() - 1) {
break;
}
}
return s.substring(longestStart, longestEnd + 1);
}
private static boolean isPalindrome(String s, int start, int end) {
for (int i = start; i < (start + end + 1) / 2; i++) {
if (s.charAt(i) != s.charAt(end + start - i)) {
return false;
}
}
return true;
}
}
第二种方法：中心扩展法
从左往右扫描字符串S，以每个字符为中心，向两边扩展构造回文子串，记录最长回文子串的起始结束位置。
Leet Code 测试耗时 49ms。
public class Solution {
public static String longestPalindrome(String s) {
if (s == null || s.length() <= 1) {
return s;
}
int longestStart = 0;
int longestEnd = 0;
int start = 0;
int end = 0;
for (int i = 0; i < s.length(); i++) {
// 回文长度为奇数
for (int j = 0; (i - j >= 0) && (i + j) < s.length(); j++) {
if (s.charAt(i - j) != s.charAt(i + j)) {
break;
}
start = i - j;
end = i + j;
}
if (end - start > longestEnd - longestStart) {
longestEnd = end;
longestStart = start;
}
// 回文长度为偶数
for (int j = 0; (i - j) >= 0 && (i + j + 1) < s.length(); j++) {
if (s.charAt(i - j) != s.charAt(i + j + 1)) {
break;
}
start = i - j;
end = i + j + 1;
}
if (end - start > longestEnd - longestStart) {
longestEnd = end;
longestStart = start;
}
}
return s.substring(longestStart, longestEnd + 1);
}
}