據(jù)我了解的問(wèn)題，我們可以在中心索引附近找到回文，并在中心的左右兩側(cè)進(jìn)行搜索。鑒于此，并且知道輸入的角落沒有回文，我們可以將邊界設(shè)置為1和length-1。注意字符串的最小和最大邊界時(shí)，我們驗(yàn)證對(duì)稱索引位置（右和左）上的字符對(duì)于每個(gè)中心位置是否都相同，直到達(dá)到最大上限中心。
外循環(huán)為O（n）（最多n-2次迭代），內(nèi)循環(huán)為O（n）（最大（n / 2）-1次迭代）
這是我使用其他用戶提供的示例的Java實(shí)現(xiàn)。
class LongestPalindrome {
/**
* @param input is a String input
* @return The longest palindrome found in the given input.
*/
public static String getLongestPalindrome(final String input) {
int rightIndex = 0, leftIndex = 0;
String currentPalindrome = "", longestPalindrome = "";
for (int centerIndex = 1; centerIndex < input.length() - 1; centerIndex++) {
leftIndex = centerIndex - 1; rightIndex = centerIndex + 1;
while (leftIndex >= 0 && rightIndex < input.length()) {
if (input.charAt(leftIndex) != input.charAt(rightIndex)) {
break;
}
currentPalindrome = input.substring(leftIndex, rightIndex + 1);
longestPalindrome = currentPalindrome.length() > longestPalindrome.length() ? currentPalindrome : longestPalindrome;
leftIndex--; rightIndex++;
}
}
return longestPalindrome;
}
public static void main(String ... args) {
String str = "HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE";
String longestPali = getLongestPalindrome(str);
System.out.println("String: " + str);
System.out.println("Longest Palindrome: " + longestPali);
}
}
其輸出如下：
marcello:datastructures marcello$ javac LongestPalindrome
marcello:datastructures marcello$ java LongestPalindrome
String: HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE
Longest Palindrome: 12345678987654321
