#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define REP(i, n) for(int i = 0, _n(n); i < _n; i++)
const int MX = 10000;
char s[MX];
int pre[MX][MX];
int dp[MX];
int main() {
scanf("%s", s);
int n = strlen(s);
// preprocessing stage, mark pre[i][j] = 1 only if substring from
i to j is a palindrome
REP(i, n) memset(pre[i], 0, sizeof(pre[i]));
REP(i, n) {
// try i as center;
pre[i][i] = 1;
// try all odd length palindromes
int l = i-1, r = i+1;
while(l>=0 && r<n && s[l]==s[r]) {
pre[l][r] = 1;
l--; r++;
}
// try all even length palindromes
l = i; r = i+1;
while(l>=0 && r<n && s[l]==s[r]) {
pre[l][r] = 1;
l--; r++;
}
}
// prints all substrings which are palindrome
/*
for(int i = 0; i < n; i++) {
for(int j = i; j < n; j++) {
if(pre[i][j]) {
for(int k = i; k <= j; k++) putchar(s[k]);
putchar('\n');
}
}
}
*/
const int INF = 1000000000;
REP(i, n) {
dp[i] = INF;
for(int x = 0; x <= i; x++) {
if(pre[x][i]) {
dp[i] = min(dp[i], (x==0)?0:(dp[x-1]+1));
}
}
}
printf("%d\n", dp[n-1]);
}
It may contain errors, i haven't tested it properly...
On Aug 3, 9:12 pm, ankit sambyal <[email protected]> wrote:
> @amit: can u supply the code for ur approach ??
--
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.
