I second that. I believe O(n^2) is a correct call.
Consider a function LONGEST_PALINDROME (left, right), where it accepts the
substring definition based on left and right, and will return the maximum
length of palindrome which can be generated from that substring:
LONGEST_PALINDROME (left, right)
result = 0 if left > right, for empty string, or even invalid substring
result = 1 if left == right, which is one character substring
result = 2 + LONGEST_PALINDROME(left+1, right-1) if str[left] ==
str[right]
result = MAX(LONGEST_PALINDROME(left+1, right), LONGEST_PALINDROME(left,
right-1)) for other cases
On 3/30/07, Muntasir Azam Khan <[EMAIL PROTECTED]> wrote:
>
> >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
>
> >
>
--
Fear of the LORD is the beginning of knowledge (Proverbs 1:7)
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
