Longest Palindromic Subsequence in Python using Memoization
Step-by-step algorithm:
- Define a recursive function, say lps(s1, s2, n1, n2) which finds the longest common subsequence among s1 and s2 where n1 is index of s1 and n2 is index of s2.
- Call the lps function with input string seq as s1 and reverse of seq as s2.
- If we reach the first index of any string, return 0
- Check if we have already computed the result for the current indices.
- If the result is already computed, return the result.
- Otherwise, if the current indices of both s1 and s2 are equal, dp[n1][n2] = 1 + lps(s1, s2, n1 – 1, n2 – 1)
- Else if the current index of both s1 and s2 are not equal, dp[n1][n2] = max(lps(s1, s2, n1 – 1, n2), lps(s1, s2, n1, n2 – 1))
- Store the above result in dp[n1][n2]
Below is the implementation of Longest Palindromic Subsequence in Python using Memoization:
# A Dynamic Programming based Python program for LPS problem
# Returns the length of the longest palindromic subsequence
# in seq
dp = [[-1 for i in range(1001)]for j in range(1001)]
# Returns the length of the longest palindromic subsequence
# in seq
def lps(s1, s2, n1, n2):
if (n1 == 0 or n2 == 0):
return 0
if (dp[n1][n2] != -1):
return dp[n1][n2]
if (s1[n1 - 1] == s2[n2 - 1]):
dp[n1][n2] = 1 + lps(s1, s2, n1 - 1, n2 - 1)
return dp[n1][n2]
else:
dp[n1][n2] = max(lps(s1, s2, n1 - 1, n2), lps(s1, s2, n1, n2 - 1))
return dp[n1][n2]
# Driver program to test above functions
seq = "w3wiki"
n = len(seq)
s2 = seq
s2 = s2[::-1]
print(f"The length of the LPS is {lps(s2, seq, n, n)}")
Output
The length of the LPS is 5
Time Complexity: O(n2), where n is the length of the input string
Auxiliary Space: O(n2)
Longest Palindromic Subsequence in Python
Longest Palindromic Subsequence (LPS) problem is about finding the longest subsequence of the given sequence which is a palindrome. In Python, the task of maximizing the number of words in a sentence can be solved by the methods of dynamic programming.
The algorithm for finding the Longest Palindromic Subsequence involves creating a table to store the lengths of the longest palindromic subsequences for different substrings of the input sequence.