对于长度为n的一个字符串A（仅包含数字，大小写英文字母），请设计一个高效算法，计算其中最长回文子串的长度。
数据范围： 
要求：空间复杂度 )
，时间复杂度 )
进阶: 空间复杂度 )
，时间复杂度
[编程题]最长回文子串
c语言 暴力方法
// 判断是否是回文
bool huiwen(char* s) {
int size = strlen(s);
int i = 0, j = size - 1;
while (i < j) {
if (s[i] != s[j]) {
return false;
}
i++;
j--;
}
return true;
}
int max(int a,int b)
{
if(a>b)
{
return a;
}
else {
return b;
}
}
int getLongestPalindrome(char* s) {
int i,j;
int size=strlen(s);
int ans=1;
for(i=0;i<size;i++)
//每一个字符向后统计字符串
{
for(j=i+1;j<size;j++)
{
//遍历所有i后面的子串
int size2=j-i+1;
char *temp=(char *)malloc(sizeof(char)*size2+1);
//把i后面的子串拷贝到temp
//s+i ,字串的首地址 ,size2: 子串的长度
strncpy(temp,s+i,size2);
if(huiwen(temp))
{
ans=max(size2,ans);
}
free(temp);
}
}
return ans;
}
发表于 2025-03-06 17:16:16
回复(0)
bool judge(char* str , int len) {
if(len<2)
return true;
if(judge(str+1, len-2) && str[0]==str[len-1])
return true;
else
return false;
}
#define MAX(a,b) (a>b?a:b)
int getLongestPalindrome(char* A ) {
int i,j,max=0;
for(i=0; i<strlen(A); i++)
for(j=strlen(A)-i; j>0; j--) {
if(judge(A+i, j)) {
max=MAX(max, j);
}
}
return max;
}
编辑于 2024-03-24 13:23:58
回复(0)
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param A string字符串
* @return int整型
*/
int getLongestPalindrome(char* A ) {
// write code here
int len = strlen(A);
int left;
int right;
if (len == 0)
return 0;
right = len - 1;
int max = 0;
int count = 0;
for (left = 0; left < len; left++) {
for (right = len - 1; right >= left; right--) {
int countl = left;
int rightr = right;
while (A[countl] == A[rightr] && countl < rightr) {
count = count + 2;
countl++;
rightr--;
if (countl == rightr) {
count++;
break;
}
}
if (countl != rightr && countl != rightr + 1)
count = 0;
if (right == left) {
count = 1;
}
if (max < count)
max = count;
count = 0;
}
}
return max;
}
发表于 2023-05-05 14:42:17
回复(0)
/* 从中间向两边扩展的思维，贪心算法，随后取最大值*/
int GetValue(char* A, int start, int end) {
int iValue1 = 0;
while ((start >= 0 && end < strlen(A)) && (A[start] == A[end])) {
iValue1 = end - start + 1;
start--;
end++;
}
return iValue1;
}
int getLongestPalindrome(char* A ) {
int iLength = strlen(A);
if (iLength == 1 || iLength == 0) {
return iLength;
}
int iValue1 = 0;
int iValue2 = 0;
int iMaxLen = 1;
for (int i = 0 ; i < iLength; i++) {
iValue1 = GetValue(A, i, i);
iValue2 = GetValue(A, i, i + 1);
if ((iValue1 >= iValue2) && (iValue1 >= iMaxLen)) {
iMaxLen = iValue1;
} else if ((iValue2 > iValue1) && (iValue2 >= iMaxLen)) {
iMaxLen = iValue2;
}
}
return iMaxLen;
}
发表于 2023-04-02 09:47:27
回复(0)
#include <stdio.h>
#include <string.h>
int getLongestPalindrome(char* A )
{
// write code here
int len=strlen(A); //字符串A的长度
int dp[len][len]; //定义状态矩阵，存放字符串A第i到j是否是回文子串，是，则dp[i][j]=1,否，为0
memset(dp, 0, sizeof(dp));//初始化dp的值为0
int ans=1;//题目给定n最小为1，因此最小的回文子串长度为1 （字符本身就是回文）
//定义边界，便于递推
//当长度为1和2时，遍历字符串，每个字符都是一个回文，因此A从i到i的状态值dp[i][i]=1
//当长度为2时，只需要比较这两个相邻字符是否相等，若是，则A从i到i+1的状态值dp[i][i+1]=1，此时更新ans=2
for(int i=0;i<len;i++){
dp[i][i] = 1;
if(i<len-1){
if(A[i]==A[i+1]){
dp[i][i+1]=1;
ans=2;
}
}
}
//从长度3到len
for(int l=3; l<=len;l++){
//区间i到i+l-1的长度为l
for(int i=0;i<len-l+1;i++){
int j=i+l-1;
//状态转移方程 判断A的i到j是否回文，必须A[i]=A[j],且，字符串i+1到j-1的子串也是回文
if(A[i]==A[j]&&dp[i+1][j-1]==1){
dp[i][j] =1;
ans=l;
}
}
}
return ans;
}
发表于 2023-03-24 11:51:29
回复(0)
int f[1005][1005];
int getLongestPalindrome(char* A ) {
// write code here
int len=strlen(A),max=0;
if(len==1)return 1;
for(int i=0;i<len;i++)f[i][i]=1;
for(int i=1;i<len;i++){
for(int j=0;j<i;j++){
if(A[i]==A[j]){
if(i==j+1){
f[j][i]=2;
}else{
if(f[j+1][i-1]>0){
f[j][i]=f[j+1][i-1]+2;
}
}
}
max=max>f[j][i]?max:f[j][i];
}
}
return max>1?max:1;
}
发表于 2023-03-23 11:45:40
回复(0)
int getLongestPalindrome(char* A ) {
// write code here
int n = strlen(A);
bool dp[n][n];
memset(dp,0,sizeof (dp));
int res = 1;
for (int d = 0; d < n; ++d) {
for (int i = 0; i < n-d; ++i) {
int j = i+d;
if (A[i] == A[j]){
if (d==1||d==0){
dp[i][j] = true;
}else {
dp[i][j] = dp[i+1][j-1];
}
if (dp[i][j]){
res = res > (d+1) ? res : (d+1);
}
}
}
}
return res;
}
发表于 2022-03-02 21:50:51
回复(0)
int getLongestPalindrome(char* A ) {
int len=strlen(A),max=1,flag=0;
for(int i=0;i<=len;i++){
for(int j=len-1;j>=i+max;j--){
if(*(A+i)==*(A+j)){
flag=1;
for(int t=1;t<=(j-i)/2;t++){
if(*(A+i+t)!=*(A+j-t)){
flag=0;
break;
}
}
}
if(flag==1){
max=j-i+1;
flag=0;
break;
}
}
}
return max;
}
发表于 2021-12-04 12:21:31
回复(0)
int getLongestPalindrome(char* A ) {
// write code here
int ALength = strlen(A);
int start = 0;
int i = 0;
int j = 0;
char* p = A;
char* pend;
int maxLength = 0;
int thisLength = 0;
if (ALength <= 1)
{
return ALength;
}
for (start = 0; start < ALength - 1; start++)
{
for(i = 2; i <= ALength - start; i++)
{
p = A+start;
j = i / 2;
pend = p + i - 1;
thisLength = i;
while(j != 0)
{
j--;
if(*pend != *p)
{
thisLength = 0;
break;
}
else
{
pend--;
p++;
}
}
if(thisLength > maxLength)
{
maxLength = thisLength;
}
}
}
return maxLength;
}
// write code here
int ALength = strlen(A);
int start = 0;
int i = 0;
int j = 0;
char* p = A;
char* pend;
int maxLength = 0;
int thisLength = 0;
if (ALength <= 1)
{
return ALength;
}
for (start = 0; start < ALength - 1; start++)
{
for(i = 2; i <= ALength - start; i++)
{
p = A+start;
j = i / 2;
pend = p + i - 1;
thisLength = i;
while(j != 0)
{
j--;
if(*pend != *p)
{
thisLength = 0;
break;
}
else
{
pend--;
p++;
}
}
if(thisLength > maxLength)
{
maxLength = thisLength;
}
}
}
return maxLength;
}
发表于 2021-11-20 15:16:28
回复(0)
问题信息
通过挑战的用户
查看代码-
2023-03-12 11:49:39 -
2023-03-11 21:34:19
-
2023-03-09 16:16:00
-
2023-03-08 15:23:26 -
2023-03-08 15:07:36
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
