对于长度为n的一个字符串A(仅包含数字,大小写英文字母),请设计一个高效算法,计算其中最长回文子串的长度。
数据范围:
要求:空间复杂度 ,时间复杂度
进阶: 空间复杂度 ,时间复杂度
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; }
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; }
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; }
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; }