the idea for O(|S|^2) is as follows....
Let string be s[1..n]
p[i][j]=1 if s[i...j] is a palindrome
p[i][j]=0 otherwise.
we can precalculate table p[i][j] as follows..in O(|s|^2)
p[i][i]= 1
p[i][i+1]=1 if s[i]==s[i+1], 0 otherwise
for all others..
p[i][j]= (s[i]==s[j] && p[i+1][j-1]==1).
now let m[i] represents the minimum number of palindromes needed to
represent s[1...i],
so m[n] is our required answer..
now...let us define m[i] recursively as follows..
m[0]=0, m[1]=1
m[i]=min { m[j-1]+1 where 1<=j<=i && p[j][i]==1}
what it actually says is that...we can go through all possible palindromes
which can be at the end of s[1...i],and check choosing which one is the best
option for us...
i guess its correct...if there is any problem with it then do suggest....
On Tue, Nov 16, 2010 at 7:56 PM, cheng lee <[email protected]> wrote:
> how to do that in O(|s|^2)?
>
> 2010/11/16 anoop chaurasiya <[email protected]>
>
>> will O(|s|^2) dp work....or u need something more efficient than that....
>>
>>
>> On Tue, Nov 16, 2010 at 1:51 PM, lichenga2404 <[email protected]>wrote:
>>
>>> A palindrome is a string which is identical to itself in reverse
>>> order. For example
>>> \ABAAABA" is a palindrome. Given a string, we'd like to break it up
>>> into the small-
>>> est possible number of palindromes. Of course, any one-character
>>> string is a palindrome
>>> so we can always break a length n string into n palindromes. Design an
>>> e cient al-
>>> gorithm to determine the minimum number of palindromes in a
>>> decomposition for a
>>> given string, and analyze the running time. You may assume you are
>>> given a proce-
>>> dure Palindrome(S) which runs in time O(jSj) and returns true if and
>>> only if S is a
>>> palindrome.
>>>
>>> How to solve this problem with the dynamic programming method?
>>>
>>> --
>>> 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]<algogeeks%[email protected]>
>>> .
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>>
>>
>>
>> --
>> Anoop Chaurasiya
>> CSE (2008-2012)
>> NIT DGP
>>
>> --
>> 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]<algogeeks%[email protected]>
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> licheng
>
> --
> 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]<algogeeks%[email protected]>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
Anoop Chaurasiya
CSE (2008-2012)
NIT DGP
--
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.
