首页 > 试题广场 > 最长回文子串
[编程题]最长回文子串
  • 热度指数:34041 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解

对于一个字符串,请设计一个高效算法,计算其中最长回文子串的长度。

给定字符串A以及它的长度n,请返回最长回文子串的长度。

示例1

输入

"abc1234321ab",12

输出

7
头像 WosAlan
发表于 2020-11-22 14:47:41
暴力解法 直接判断每一个子串是不是回文子串,然后取其中最长的值返回 public class Palindrome { public int getLongestPalindrome(String A, int n) { int maxLen = 0; //暴 展开全文
头像 2021找工作
发表于 2020-09-30 00:05:44
这个题目用到了动态规划的思想具体注意字符串的遍历顺序一定是从后向前的,因为这样才能解决之前没有计算而直接出答案的问题。这里的dp数组比较难想,是应该存储所经过的子字符串是否是回文数 public static int getLongestPalindrome(String A, int n) { 展开全文
头像 牛客232971778号
发表于 2020-09-13 22:26:50
思路1(动态规划,O(n^2))从第一个字符往后遍历,把每个字符都当作中心去向两边扩散,依次比较对称位置是否相等,当碰到左右边界停下。注意要分奇偶子串两种情况。 代码1 class Palindrome: def getLongestPalindrome(self, A, n): 展开全文
头像 仲夏的田野
发表于 2021-02-03 21:04:45
解法1:暴力解法 直接判断每一个子串是不是回文子串,然后取其中最长的值返回 public class Palindrome { public int getLongestPalindrome(String A, int n) { int maxLen = 0; 展开全文
头像 xuwenshg
发表于 2020-09-14 13:23:01
题目描述对于一个字符串,请设计一个高效算法,计算其中最长回文子串的长度。给定字符串A以及它的长度n,请返回最长回文子串的长度。 解题思路:暴力穷举法的基础上,改进了回文子串的判断方法,一般的判断一个字串是否回文需要的时间复杂度是O(n)可以在扫描的过程中记录下某个字串的是否满足回文,为判断其他字串是 展开全文
头像 Edwin_Xu
发表于 2020-09-01 00:41:09
public int getLongestPalindrome(String s,int n) { StringBuilder sb = new StringBuilder(); sb.append("$#"); //这里可以在前后添加字符防止后面 展开全文
头像 人定胜天~
发表于 2021-01-09 16:37:35
class Solution { public: //思路:对于一个子串而言,如果它是回文串,并且长度大于2,那么将它首尾的两个字母去除之后,它仍然是个回文串。 //对于长度为1的子串,它显然是个回文串;对于长度为2 的子串, //只要它的两个字母相同,它就是一个回文串。用于 展开全文
头像 北晨LPL
发表于 2020-08-25 21:22:18
# -*- coding:utf-8 -*- class Palindrome: def getstr(self,A,n): re = [] for i in range(n): for j in range(i + 1,n + 1) 展开全文
头像 牛客339312663号
发表于 2020-11-13 15:13:58
思路: 动态规划 时间复杂度(O^2) 回文的长度可能会出现奇偶数,分两步分别找寻奇偶最大回文字符。 第一步:两个指针,L指向最左边,R指向比L多1,如果指向的字符相等分别向两边扩散继续比较, 如果R-L+1 > max,重新赋值max,因为从0开始所以加1; 第二部:两个指针, 展开全文
头像 王海金
发表于 2021-02-23 16:54:53
提供一个新思路,通过回文字符串的特性,正反读取都相同,可以将字符串逆转后,求取最长公共子串,但可能会出现其他部分重置与另一部分相同,所以需要对比找到最长公共子串的索引与原索引相加是否为字符串长度-1,即 i+j-tmp[j+1]+1== len(A)-1,如果相等,则更新最长回文子串 func ge 展开全文