当前位置: 首页 > 面试题库 >

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

萧越泽
2023-03-14
问题内容

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

我想到了一个解决方案,但它的运行时间为O(n ^ 2)

算法1:

步骤:这是一种蛮力方法

  1. 对于i = 1到i小于array.length的2个for循环
  2. 对于j = i + 1到j小于 array.length的-1
  3. 这样,您可以从数组中获取所有可能组合的子字符串
  4. 具有回文功能,可检查字符串是否为回文
  5. 因此,对于每个子字符串(i,j)都调用此函数(如果它是回文)将其存储在字符串变量中
  6. 如果找到下一个回文子字符串,并且该子字符串大于当前子字符串,则将其替换为当前子字符串。
    最后,您的字符串变量将得到答案
    问题:1.该算法运行时间为O(n ^ 2)。

算法2:

  1. 反转字符串并将其存储在不同的数组中
  2. 现在找到两个数组之间最大的匹配子字符串
  3. 但这也需要O(n ^ 2)时间
    你们能想到一种运行时间更好的算法吗?如果可能的话O(n)时间

问题答案:

您可以使用最长的回文Manacher算法的O(n)时间!它的实现可以在这里 找到。

对于输入,String s = "HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE"它将找到正确的输出1234567887654321



 类似资料:
  • 本文向大家介绍请编写一个C 函数,该函数将给定的一个字符串转换成整数。相关面试题,主要包含被问及请编写一个C 函数,该函数将给定的一个字符串转换成整数。时的应答技巧和注意事项,需要的朋友参考一下 【参考答案】

  • 本文向大家介绍请编写一个C 函数,该函数将给定的一个整数转换成字符串。相关面试题,主要包含被问及请编写一个C 函数,该函数将给定的一个整数转换成字符串。时的应答技巧和注意事项,需要的朋友参考一下 【参考答案】 void IntToCharChange(int num, char* pval) { char strval[100]; int i , j; int val0 = 0; int val1

  • 问题内容: 在Python中,我想编写一个返回另一个函数的函数。返回的函数应该可以通过参数调用,并返回高度和半径为圆柱的体积。 我知道如何从Python中的函数返回 值 ,但是如何返回 另一个函数 ? 问题答案: 使用Python尝试一下: 这样使用它,例如与和: 注意,返回一个函数很简单,只需在函数内部定义一个新函数,然后在最后返回它- 小心地为每个函数传递适当的参数。仅供参考,从另一个函数返回

  • 本文向大家介绍请编写一个C 函数,该函数在一个字符串中找到可能的最长的子字符串,该字符串是由同一字符组成相关面试题,主要包含被问及请编写一个C 函数,该函数在一个字符串中找到可能的最长的子字符串,该字符串是由同一字符组成时的应答技巧和注意事项,需要的朋友参考一下 的。 【参考答案】 int C hildString(char*p) // 自己写 { char q =p; int s tringle

  • 本文向大家介绍请编写一个C 函数,该函数在给定的内存区域搜索给定的字符,并返回该字符所在位置索引值。相关面试题,主要包含被问及请编写一个C 函数,该函数在给定的内存区域搜索给定的字符,并返回该字符所在位置索引值。时的应答技巧和注意事项,需要的朋友参考一下 【参考答案】 int s earch(char* cpSource, intn , char ch) // 起始地址,搜索长度,目标字符 { i

  • 给定一个字符串数组,单词,返回该数组,其中包含所有偶数长度的字符串,并将其替换为空字符串。 如何返回字符串?我需要返回字符串以便为偶数打印空白,但现在我只是返回一个计数。这是我的代码,我认为一切都是正确的,我只是不知道如何返回它?