Dynamic Programming in Python: Optimizing Programs for Efficiency/

...

/

Solution Review: Longest Palindromic Subsequence

Solution Review: Longest Palindromic Subsequence

In this lesson, we will see the solution to the longest palindromic subsequence problem and see another similar problem to the longest palindromic substring.

We'll cover the following...

Solution: Using longest common subsequence function

Press + to interact
main.py
lcs.py
from lcs import LCS
# call longest common subsequence function as follows: 
#   LCS(str1, str2)
#   returns integer for length of the longest common subsequence in str1 and str2
def LPS(str):
    return LCS(str, str[::-1])
print(LPS("racercar"))

Explanation

That’s it. All the magic happens in the LCS function and we have already seen how that function works in the previous solution review. We have simply called the LCS function with the actual string str and its reversed form str[::-1]. Let’s see why this works.

We know that we wrote our LCS algorithm to compare characters from the start of the strings towards the end. In this case, we want to compare the same string starting from the opposite ends. One way to exploit our implementation of LCS is to simply pass it the original string and its reversed version.

Time and space complexity

Time taken in reversing a string is O(n), while we know that LCS has a time complexity of O(nm) given strings of sizes n and m. Since here we have two versions of the same string, they will have the same length, n. Thus, the time complexity would be O(n2^2). Similarly, the space complexity would also be O(n2^2 ...