编写一个函数，该函数返回给定字符串中最长的回文

Question

例如字符串“ abaccddccefe”中的“ ccddcc”

我想到了一个解决方案，但它的运行时间为O（n ^ 2）

算法1：

步骤：这是一种蛮力方法

对于i = 1至i小于array.length的2个for循环，

对于j = i + 1至j小于 array.length的-1

这样，您可以从数组中获取所有可能组合的子字符串

具有回文功能，可检查字符串是否为回文

因此，对于每个子字符串（i，j）都调用此函数（如果它是回文）将其存储在字符串变量中

如果找到下一个回文子字符串，并且该子字符串大于当前子字符串，则将其替换为当前子字符串。

最后，您的字符串变量将得到答案

问题：1.该算法运行时间为O（n ^ 2）。

算法2：

反转字符串并将其存储在不同的数组中

现在找到两个数组之间最大的匹配子字符串

但这也需要O（n ^ 2）时间

你们能想到一种运行时间更好的算法吗？如果可能的话O（n）时间

Answer 1

您可以使用最长的回文Manacher算法的O(n)时间！它的实现可以在这里和这里找到。对于输入，String s = "HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE"它将找到正确的输出1234567887654321。

Answer 2

据我了解的问题，我们可以在中心索引附近找到回文，并在中心的左右两侧进行搜索。鉴于此，并且知道输入的角落没有回文，我们可以将边界设置为1和length-1。注意字符串的最小和最大边界时，我们验证对称索引位置（右和左）上的字符对于每个中心位置是否都相同，直到达到最大上限中心。外循环为O（n）（最多n-2次迭代），内循环为O（n）（最大（n / 2）-1次迭代）这是我使用其他用户提供的示例的Java实现。class LongestPalindrome {&nbsp; &nbsp; /**&nbsp; &nbsp; &nbsp;* @param input is a String input&nbsp; &nbsp; &nbsp;* @return The longest palindrome found in the given input.&nbsp; &nbsp; &nbsp;*/&nbsp; &nbsp; public static String getLongestPalindrome(final String input) {&nbsp; &nbsp; &nbsp; &nbsp; int rightIndex = 0, leftIndex = 0;&nbsp; &nbsp; &nbsp; &nbsp; String currentPalindrome = "", longestPalindrome = "";&nbsp; &nbsp; &nbsp; &nbsp; for (int centerIndex = 1; centerIndex < input.length() - 1; centerIndex++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; leftIndex = centerIndex - 1;&nbsp; rightIndex = centerIndex + 1;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; while (leftIndex >= 0 && rightIndex < input.length()) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (input.charAt(leftIndex) != input.charAt(rightIndex)) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; break;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; currentPalindrome = input.substring(leftIndex, rightIndex + 1);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; longestPalindrome = currentPalindrome.length() > longestPalindrome.length() ? currentPalindrome : longestPalindrome;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; leftIndex--;&nbsp; rightIndex++;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return longestPalindrome;&nbsp; &nbsp; }&nbsp; &nbsp; public static void main(String ... args) {&nbsp; &nbsp; &nbsp; &nbsp; String str = "HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE";&nbsp; &nbsp; &nbsp; &nbsp; String longestPali = getLongestPalindrome(str);&nbsp; &nbsp; &nbsp; &nbsp; System.out.println("String: " + str);&nbsp; &nbsp; &nbsp; &nbsp; System.out.println("Longest Palindrome: " + longestPali);&nbsp; &nbsp; }}其输出如下：marcello:datastructures marcello$ javac LongestPalindromemarcello:datastructures marcello$ java LongestPalindromeString: HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDELongest Palindrome: 12345678987654321