编写一个函数，该函数返回给定字符串中最长的回文
例如字符串“ 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）时间
回答：
您可以使用最长的回文Manacher算法的O(n)时间！它的实现可以在这里 找到。
对于输入，String s = "HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE"它将找到正确的输出1234567887654321。
以上是 编写一个函数，该函数返回给定字符串中最长的回文 的全部内容， 来源链接： utcz.com/qa/403931.html
