Let the given string have a length N and contain characters indexed
from 1 on to N.
Let,
f(n) denote the minimum number of cuts that you need to make such that
each substring is a palindrome, considering only the prefix containing
n characters.
f(0) = -1
f(n) = min( f(x) + 1 ), take x such that 0 <= x < n and p(x+1, n)=1.
where p(x, n) = { 1, if substring containing characters from position
x to n is a palindrome
0, otherwise
You should calculate p(n, x) beforehand,
p(i, j) for all i, j such that 1 <= i <= j <= n can be calculated in
O(n^2),
Just try all characters as center and try growing the palindrome
towards right and left simultaneously. On the first mismatch before
right and left characters stop and try other
characters as center. While you do this you may mark sol[i][j] as 1
if substring(i, j) is a palindrome.
I hope this is the optimal way of solving this problem.
This has a complexity of O(n^2).
If anyone has something better to add to this please comment.
On Aug 3, 9:07 am, ankit sambyal <[email protected]> wrote:
> You are given a large string. You need to cut the string into chunks such
> that each substring that you get is a palindrome. Remember that each 1
> length string is always a palindrome. You need to find the minimum number of
> cuts that you need to make such that each substring is a palindrome.
--
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.
