• Guest, before posting your code please take these rules into consideration:
    • It is required to use our BBCode feature to display your code. While within the editor click < / > or >_ and place your code within the BB Code prompt. This helps others with finding a solution by making it easier to read and easier to copy.
    • Don't share a wall of code. All we want is the problem area, the code related to your issue.


    To learn more about how to use our BBCode feature, please click here.

    Thank you, Code Forum.

Python The longest palindrome sequence

Hilton D

Hilton D

Coder
A palinadrome is a nonempty string that reads the same forward and backward across some alphabet. Palindromes include all strings of length one, civic, racecar, and aibohphobia (fear of palindromes). Provide an efficient approach for determining the longest palindrome that is a subsequence of the supplied input string. Given the input "character," your algorithm should return "caac."
Code: 
def mylongest(self, i, j):
    if j - i <= 1:
        return j-i
    else:
        if self.sequence[i] == self.sequence[j]:
            return self.mylongest(i+1,j-1) + 2
        else:
            return max (self.mylongest(i+1, j), self.mylongest(i, j-1))
I now understand how to calculate the length of the result. How can I obtain the result sequence? I'm checking all 2n combinations; according to this source, it's the least efficient algorithm, and it recommends using a dynamic program to solve this problem in O(n2), is that correct?
 
Sort by date Sort by votes
Hilton D said:
A palinadrome is a nonempty string that reads the same forward and backward across some alphabet. Palindromes include all strings of length one, civic, racecar, and aibohphobia (fear of palindromes). Provide an efficient approach for determining the longest palindrome that is a subsequence of the supplied input string. Given the input "character," your algorithm should return "caac."
Code: 
def mylongest(self, i, j):
    if j - i <= 1:
        return j-i
    else:
        if self.sequence[i] == self.sequence[j]:
            return self.mylongest(i+1,j-1) + 2
        else:
            return max (self.mylongest(i+1, j), self.mylongest(i, j-1))
I now understand how to calculate the length of the result. How can I obtain the result sequence? I'm checking all 2n combinations; according to this source, it's the least efficient algorithm, and it recommends using a dynamic program to solve this problem in O(n2), is that correct?
Click to expand...
My first question:
Are you required to output the length of the longest palindrome, or the actual string of the palindrome?
 
Upvote 0 Downvote
Top Bottom