首页 > 试题广场 >

最长回文子串

[编程题]最长回文子串
  • 热度指数：220262 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解

对于长度为n的一个字符串A（仅包含数字，大小写英文字母），请设计一个高效算法，计算其中最长回文子串的长度。


数据范围：
要求：空间复杂度 ，时间复杂度
进阶:  空间复杂度 ，时间复杂度
示例1

输入

"ababc"

输出

3

说明

最长的回文子串为"aba"与"bab"，长度都为3
示例2

输入

"abbba"

输出

5
示例3

输入

"b"

输出

1
算法知识视频讲解
添加回答
C
一个优雅的程序猿头像 一个优雅的程序猿 
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)
C
快支棱起来的回笼觉觉主很调皮头像 快支棱起来的回笼觉觉主很调皮
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @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)
C
我是小安哥头像 我是小安哥
/* 从中间向两边扩展的思维，贪心算法，随后取最大值*/
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)
C
笑个不停头像 笑个不停
#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)
C
牛客684667698号头像 牛客684667698号 
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)
C
wxrg2012头像 wxrg2012 
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)
C
牛客285751789号头像 牛客285751789号 
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)
C
牛客514997292号头像 牛客514997292号
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;

}
发表于 2021-11-20 15:16:28 回复(0)
提交观点

问题信息

动态规划 字符串
来自：经典算法题精讲（四）-...
上传者：牛客301499号
难度：
9条回答 63039浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号