>I think the problem can be solved by simply removing 'i' letters from the
>string and check if that is a palendrome. where i would go from 1 to lenght.
You are almost there. My solution is as follows,
Given a string str check if the first character of str is the same as the last
character.
If it is not, we call the same function again, once with the first character
removed ("ADAM"->"DAM")
and again with the last character removed ("ADAM"->"ADA"). We return the
maximum of these two values.
If, on the other hand, the first and last characters match, we call the same
function again with the first and
last characters removed ("ADA"->"D"), add two (for the first and last chars)
and return the result. And of course,
the base case is that zero length strings are zero length palindromes.
Now, this solution will give you the correct answer but it will undoubtedly
time out as you observed in your post.
If you look carefully, you will see that we end up checking the same parts of
the string over and over again.
This is clearly a dynamic programming problem. A real expert programmer would
make a bottom up
dynamic programming solution using two for loops, but I simply wrote a
recursive function and used
a 2D array to memoize the results. That was fast enough and, if I am not
mistaken, this has a complexity
of O(n^2) where n is the length of the string.
Muntasir
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
