My code using dp takes leeser amount of time than a few submitted
solutions still submission says TLE ..
Kindly help!!
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <stdio.h>
using namespace std;
int A[1001][1001];
bool if_palindrome( string s, int i, int j )
{
if( s[i] == s[j] ){
if((i+1)<=(j-1)){
if(A[i+1][j-1]==1){
A[i][j]= 1;
return 1;
} else
return 0;
} else {
A[i][j]=1;
return 1;
}
} else
return 0;
}
int count( string s, int i, int j){
int length = s.size()-1;
int dp[length+2];
dp[0]=1;
dp[-1]=1;
for( int m = 1; m <= length; m++ ) {
dp[m]=0;
for ( int n = m; n >= 0; n-- ) {
if( if_palindrome(s,n,m) ==1 )
dp[m] += dp[n-1];
}
}
return dp[length];
}
int main()
{
A[0][0]=1;
char s[1001];
scanf("%s",s);
int length = strlen(s)-1;
int h = count(s,0,length);
printf("%d\n", (h%1000000007) );
return 0;
}
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
