对于一个字符串，请设计一个高效算法，计算其中最长回文子串的长度。
给定字符串A以及它的长度n，请返回最长回文子串的长度。
[编程题]最长回文子串
动态规划：
public int getLongestPalindrome(String A, int n) {
// 第 i 个字符到第 j 个字符是否是回文串
boolean[][] dp = new boolean[n][n];
int max = 0;
// 字符串首尾字母长度差 (d = j-i)
for (int d = 0; d < n; d++) {
// 字符串起始位置 i
for (int i = 0; i < n-d; i++) {
// 字符串结束位置 j
int j = i+d;
// 如果字符串 i 到 j 的首尾相等，再根据字符串 i-1 到 j-1 来确定，即得到递推公式
if(A.charAt(i) == A.charAt(j)) {
if(d == 0 || d == 1) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i+1][j-1];
}
if(dp[i][j]) {
// 更新最大长度
max = Math.max(max, d+1);
}
}
}
}
return max;
}
发表于 2017-08-23 15:43:46
回复(8)
从头到尾扫描字符串，每增加一个新的字符，判断以这个字符结尾，且长度为maxLen+1或者maxLen+2的子串是否为回文，如果是，更新。
class Solution:
def getLongestPalindrome(self, A, n):
maxLen=1
if A==A[::-1]:return n
for i in range(n):
if i-maxLen>=1 and A[i-maxLen-1:i+1]==A[i-maxLen-1:i+1][::-1]:
maxLen+=2
continue
if i-maxLen>=0 and A[i-maxLen:i+1]==A[i-maxLen:i+1][::-1]:
maxLen+=1
return maxLen
编辑于 2019-03-05 13:18:58
回复(1)
import java.util.*; public class Solution { public int getLongestPalindrome(String A, int n) { // write code here int[][] dp = new int[n][n]; int max = 1; for (int i = 0; i < n; ++i) { dp[i][i] = 1; } char[] a = A.toCharArray(); for (int len = 2; len <= n; ++len) { for (int i = 0; i <= n - len; ++i) { int j = i + len - 1; if (len == 2 && a[i] == a[j]) { dp[i][j] = len; max = 2; continue; } if (a[i] == a[j] && dp[i + 1][j - 1] != 0) { dp[i][j] = len; max = len; } } } return max; } }
动态规划
1.dp[i][j]表示，若i到j已经是回文串了，那么dp[i][j]是回文串的长度，否则为0；
2.初始时dp[i][i]=1，i=0,2,3...n-1；
3.递归公式，len>2时，当dp[i+1][j-1]!=0,且a[i]==a[j]时，dp[i][j] = j-i+1+dp[i+1][j-1],
否则dp[i][j]=0，i<j。这是一个从已知回文串往两边展开的过程。当len=2时，特殊处理一下，因为当len=2时，dp[i+1][j-1]会访问到dp矩阵的左下方，我们没对那个位置做初始化处理，因此不能直接用递推公式
发表于 2016-09-13 10:36:41
回复(4)
import java.util.*;
public class Solution {
//判断回文的函数
public boolean isHuiWen(String A, int n){
int k = n / 2;
for (int i = 0; i < k; ++i)
{
if (A.charAt(i) != A.charAt(n-1-i))
return false;
}
return true;
}
public int getLongestPalindrome(String A, int n) {
int maxlen=0;
for(int i=0 ;i< n ;i++){
for(int j=i+1 ;j<=n ;j++){
//两层循环遍历出所有的子串，并且逐一判断是否是回文
if(isHuiWen(A.substring(i, j),j-i)){
if(j-i>maxlen)
maxlen=j-i;
}
}
}
return maxlen;
}
}
编辑于 2016-04-04 23:09:12
回复(8)
时间复杂度有点大，但是挺好懂的。。
class Solution {
public:
bool pan(string a,int start,int end){
//判断是否回文
bool flag=true;
while(start<=end){
if(a[start]!=a[end]){
flag=false;
break;
}
start++;
end--;
}
return flag;
}
int getLongestPalindrome(string A, int n) {
int max=-1;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(A[i]==A[j]&&pan(A,i,j)&&j-i+1>max){
max=j-i+1;
}
}
}
return max;
}
};
发表于 2018-02-16 15:49:40
回复(0)
//直接暴力，适用于求长度以及具体回文串
class Solution {
public:
int getLongestPalindrome(string A, int n) {
// write code here
int start,maxlength=0;
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
{
int tmp1,tmp2;
for(tmp1=i,tmp2=j;tmp1<tmp2;tmp1++,tmp2--)
{
if(A[tmp1]!=A[tmp2])
break;
}
if(tmp1>=tmp2&&j-i>=maxlength)
{
maxlength=j-i+1;
start=i;
}
}
return maxlength;
}
};
发表于 2018-02-12 09:33:18
回复(1)
哪位大神帮我看看为什么只通过了50%，
"acbdcbbbdbdaaccbcacdacdccababcddabddaaaaaaabdbabcdddaacabacbacbbdabdacddbbadaacbbdcbccacacdabcabacacbbbdcccacdcdcdcbcbabdcdacdddbbabcaccddddddabdacaabccdcabcbcbabacaaaccaccaddabbdadcdacdcdbaadbcabdcdcaaacbcadccbbddbaddcaddcaadcbbcbbdcbdadcddabdddcdbddbbdabaaddcaadd",265
上面这个用例应该输出7，我的输出为8
import java.util.*;
import java.lang.*;
public class Solution {
//求a和b的最长公共子字符串长度
public int lcs(String a, String b) {
int max_len = 0;
int[][]dp = new int[a.length() + 1][b.length() + 1];
for (int i = 1; i <= a.length(); i++) {
for (int j = 1; j <= b.length(); j++) {
if (a.charAt(i - 1) == b.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
if (dp[i][j] > max_len)
max_len = dp[i][j];
}
}
}
return max_len;
}
public int getLongestPalindrome(String A, int n) {
// write code here
String B = new StringBuilder(A).reverse().toString();
return lcs(A, B);
}
}
编辑于 2017-05-12 16:09:27
回复(8)
寻找字符串中最长的回文串
改进版动态规划，时间复杂度O(n*n),空间复杂度O(n)
从字符串后面开始探索
whetherSolution[j]为1表示A[i,j+1]为回文串
循环过程中，在whetherSolution里面比当前j小的whetherSolution的标记都为上一个i的
（除了i，因为A[i,i+1]单个字符为回文串）
如果得到一个回文串，和过程中保存的最长回文串比较长度。
这个等号是为了取到长度相等时排在前面的回文串。如果去掉是取到排在后面的
def getLongestPalindrome(self, A, n):
if n <= 1:
return n
whetherSolution = [0 for i in range(n)]
theSolutionMax = 1
whetherSolution[-1] = 1
for i in range(n - 2, -1, -1):
whetherSolution[i] = 1
for j in range(n - 1, i, -1):
if whetherSolution[j - 1] and A[i] == A[j]:
whetherSolution[j] = 1
if theSolutionMax < j - i + 1:
theSolutionMax = j - i + 1
else:
whetherSolution[j] = 0
return theSolutionMax
编辑于 2018-09-23 11:57:37
回复(1)
没用dp和二分hash，直接暴力了，复杂度应该是n方，注意有aba和baab这两种情况，所以i只能每次增加0.5
class Solution {
public:
int getLongestPalindrome(string A, int n) {
int currentMax = 1;
int clength = 1;
for(double i=0;i<A.size();)
{
double index =1;
if(int(i*10)%10==5)
{
index=0.5;
while(1)
{
int left = i-index;
int right = i+index;
//if(index==0.5) index =1;
if(left<0||right>=A.size()||(A[left]!=A[right]))
{
break;
}
if(currentMax<=index)
{
currentMax = index+0.5;
clength = currentMax*2;
}
index++;
}
}else
{
while(1)
{
int left = i-index;
int right = i+index;
if(left<0||right>=A.size()||(A[left]!=A[right]))
{
break;
}
if(currentMax<=index)
{
currentMax = index;
clength = 2*currentMax+1;
}
index++;
}
}
i+=0.5;
}
return clength;
}
};
public:
int getLongestPalindrome(string A, int n) {
int currentMax = 1;
int clength = 1;
for(double i=0;i<A.size();)
{
double index =1;
if(int(i*10)%10==5)
{
index=0.5;
while(1)
{
int left = i-index;
int right = i+index;
//if(index==0.5) index =1;
if(left<0||right>=A.size()||(A[left]!=A[right]))
{
break;
}
if(currentMax<=index)
{
currentMax = index+0.5;
clength = currentMax*2;
}
index++;
}
}else
{
while(1)
{
int left = i-index;
int right = i+index;
if(left<0||right>=A.size()||(A[left]!=A[right]))
{
break;
}
if(currentMax<=index)
{
currentMax = index;
clength = 2*currentMax+1;
}
index++;
}
}
i+=0.5;
}
return clength;
}
};
发表于 2018-02-24 21:22:30
回复(0)
public class Solution {
public int getLongestPalindrome(String A, int n) {
int[][] dp = new int[n][n];
int max = 1;
for (int i = 0; i < n; ++i) {
dp[i][i] = 1;
}
char[] a = A.toCharArray();
for(int i=n-2;i>=0;i--){
for(int j=i;j<n;j++){
if(j>0&&dp[i+1][j-1]!=0&&a[i]==a[j]||j>0&&i==j-1&&a[i]==a[j])
dp[i][j] = 2+dp[i+1][j-1];
if(dp[i][j]>max)
max=dp[i][j];
}
}
return max;
}
}
发表于 2016-12-22 12:30:39
回复(1)
# -*- coding:utf-8 -*-
class Solution:
def getLongestPalindrome(self, A, n):
# write code here
A='#'+'#'.join(A)+'#'
n=len(A)
RL=[0]*n
MaxRight=0
pos=0
MaxLen=0
for i in range(n):
if i<MaxRight:
RL[i]=min(RL[2*pos-i], MaxRight-i)
else:
RL[i]=1
while i-RL[i]>=0 and i+RL[i]<n and A[i-RL[i]]==A[i+RL[i]]:
RL[i]+=1
if RL[i]+i-1>MaxRight:
MaxRight=RL[i]+i-1
pos=i
MaxLen=max(MaxLen, RL[i])
return MaxLen-1
# -*- coding:utf-8 -*-
class Solution:
def getLongestPalindrome(self, A, n):
# write code here
A='#'+'#'.join(A)+'#'
n=len(A)
RL=[0]*n
MaxRight=0
pos=0
MaxLen=0
for i in range(n):
if i<MaxRight:
RL[i]=min(RL[2*pos-i], MaxRight-i)
else:
RL[i]=1
while i-RL[i]>=0 and i+RL[i]<n and A[i-RL[i]]==A[i+RL[i]]:
RL[i]+=1
if RL[i]+i-1>MaxRight:
MaxRight=RL[i]+i-1
pos=i
MaxLen=max(MaxLen, RL[i])
return MaxLen-1
#搬的，参考了网上的manacher算法的文章
发表于 2016-05-14 09:06:47
回复(0)
中心扩展法
import java.util.*;
public class Solution {
public int getLongestPalindrome(String A, int n) {
// write code here
int res = 0;
for (int i = 0;i < A.length();i++) {
res = Math.max(spread(A, i, i), res);
}
for (int j = 0;j < A.length()-1;j++) {
if (A.charAt(j) == A.charAt(j+1)) {
res = Math.max(spread(A, j, j+1), res);
}
}
return res;
}
public int spread(String A, int start, int end) {
while (start >= 0 && end < A.length() && A.charAt(start) == A.charAt(end)) {
start--;
end++;
}
return end-start-1;
}
}
发表于 2021-01-04 22:26:22
回复(0)
import java.util.*;
public class Solution {
public int getLongestPalindrome(String A, int n) {
int maxCount = 0;
for (int i = 1; i < A.length() ; i++){
int left = i -1;
int right = i +1;
int count = 1;
maxCount = getMaxCount(A, maxCount, left, right, count);
left = i -1;
right = i;
count = 0;
maxCount = getMaxCount(A, maxCount, left, right, count);
}
// write code here
return maxCount;
}
private int getMaxCount(String A, int maxCount, int left, int right, int count) {
while (left>= 0 && right <= A.length()-1 && A.charAt(left) == A.charAt(right)){
left--;
right++;
count+=2;
}
maxCount = Math.max(count,maxCount);
return maxCount;
}
}
发表于 2020-11-08 21:53:32
回复(0)
class Solution {
public:
int getLongestPalindrome(string s, int n) {
int res=0;int l,r;
for(int i=0;i<n;i++)
{
l=i-1; r=i+1;
while(l>=0&&r<=n-1&&s[l]==s[r])
{
res=max(res,r-l+1);
l--;r++;
}
l=i;r=i+1;
while(l>=0&&r<=n-1&&s[l]==s[r])
{
res=max(res,r-l+1);
l--;r++;
}
}
return res;
}
};//借鉴某位大神的写法写了一遍
发表于 2020-09-04 17:00:20
回复(0)
暂时先写了两种思路：
思路一：直接暴力，遍历每个i,j，判断i到j是否是回文，如果是，记录最长的。
class Solution {
public:
bool isSolution(string A, int l, int r){
while(l < r){
if(A[l++] != A[r--])
return false;
}
return true;
}
int getLongestPalindrome(string A, int n) {
// write code here
int res = 0;
for(int i = 0; i < n-1; i++){
for(int j = i+1; j < n; j++){
if(isSolution(A, i, j) && j-i+1 > res)
res = j-i+1;
}
}
return res;
}
}; 思路二：先找到回文的中心，然后向两端扩散。分为两种情况：奇数的回文以及偶数的回文。
class Solution {
public:
int getLongestPalindrome(string A, int n) {
// write code here
int res = 0;
for(int i = 0; i < n; i++){
int tmp1 = 1;
int tmp2 = 2;
int l, r;
l = i-1;
r = i+1;
while(l >= 0 && r < n && A[l] == A[r]){
tmp1 += 2;
l--;
r++;
}
l = i-1;
r = i+2;
while(l >= 0 && r < n && A[l] == A[r]){
tmp2 += 2;
l--;
r++;
}
res = max(res, tmp1);
if(A[i] == A[i+1])
res = max(res, tmp2);
}
return res;
}
};
发表于 2020-08-30 16:45:19
回复(0)
class Solution {
public:
int getLongestPalindrome(string A, int n) {
if (n < 2) return n;
int max = 1;
for (int i = 0; i < n; i++) {
for (int j = 1; i-j >= 0 && i+j < n; j++)
{
if (A[i-j] == A[i+j]) {
int t = j*2 + 1;
max = t > max ? t : max;
} else
break;
}
for (int j = 0; i-j-1 >= 0 && i+j <n; j++) {
if (A[i-j-1] == A[i+j]) {
int t = j*2 + 2;
max = t > max ? t : max;
} else
break;
}
}
return max;
}
};
发表于 2020-03-29 00:56:00
回复(0)
//详情请点击博客链接（链接在最下方）
import java.util.*;
public class Solution {
public int getLongestPalindrome(String A, int n) {
// write code here
int count=0; //记录每次字符串的长度
int max=0; //记录最大字符串的长度
for(int i=0;i<n;i++){
for(int j=i+1;j<=n;j++){
String s=A.substring(i,j);//通过for截取出所有可能出现的字符串
if(isPalindromic(s)){//进行判断：2步骤
count=s.length();
if(max<count){ //进行判断：3步骤
max=count;
}
}
}
}
return max;
}
public static boolean isPalindromic(String s) {
int i = 0;
int j = s.length() - 1;
while (i <= j) {
//取出新得到的字符串挨个字符进行比较
if (s.charAt(i) != s.charAt(j)) {
return false;
}
i++;
j--;
}
return true;
}
}
————————————————
版权声明：本文为CSDN博主「峰回路转」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_44840148/article/details/105123450
发表于 2020-03-26 17:30:32
回复(0)
class Solution {
public:
int getLongestPalindrome(string str, int n) {
int max=0;
string newstr;
for(char c:str){
newstr+="#";
newstr+=c;
}
newstr+="#";
for(int i=0;i<2*n+1;i++){
for(int len=0;;len++){
if(newstr[i-len]!=newstr[i+len]||i-len<0||i+len>=2*n+1){
break;
}
if(max<len*2+1){
max=len*2+1;
}
}
}
return max/2;
}
};
没用动态规划，从中心找回文，避免考虑奇偶就在每个字符中间及首位加了#使回文串必为奇数，返回的长度除以2就行了，时间复杂度大概O(n^2)，主要容易理解
编辑于 2020-03-22 20:10:23
回复(0)
//仅作记录，方便日后查阅
class Solution {
public:
int getLongestPalindrome(string A, int n) {
// write code here
vector<vector<bool> >dp(n,vector<bool>(n,false));//dp[i][j]记录A[i]与A[j]是否相同
for(int i=0; i<n; i++)
dp[i][i]=true;//自身显然相等
int ans=1;//最短长度为1
for(int i=n-1; i>=0; i--)//从倒数第二个字符开始比较
{
for(int j=i+1; j<n; j++)//j从i+1开始
{
if(A[i]==A[j])
{
if(j==i+1)
dp[i][j]=true;//相邻的字符相等即为true
else
if(dp[i+1][j-1])//不相邻的字符，查看内侧是否相同
dp[i][j]=true;
if(dp[i][j]&&ans<j-i+1)
ans=j-i+1;
}
}
}
return ans;
}
};
发表于 2018-11-04 22:09:12
回复(0)
import java.util.*;
public class Solution {
public int getLongestPalindrome(String A, int n) {
// write code here
String str=A;
int len=str.length();
int[][] dp=new int[len][len];
int ans=1;
for(int i=0;i<len;i++){
dp[i][i]=1;
if(i<len-1){
if(str.charAt(i)==str.charAt(i+1)){
dp[i][i+1]=1;
ans=2;
}
}
}
for(int L=3;L<=len;L++){
for(int i=0;i+L-1<len;i++){
int j=i+L-1;
if(str.charAt(i)==str.charAt(j) && dp[i+1][j-1]==1){
dp[i][j]=1;
ans=L;
}
}
}
return ans;
}
}
发表于 2018-10-12 18:27:17
回复(0)
问题信息
通过挑战的用户
查看代码-
2021-01-24 23:25:09
-
2021-01-24 23:24:07
-
2021-01-24 23:14:57
-
2021-01-24 22:32:48 -
2021-01-24 21:57:31
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客网公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802(电话) admin@nowcoder.com
- 牛客科技© All rights reserved
- 京ICP备14055008号-4 增值电信业务经营许可证
-
京公网安备 11010502036488号
