Longest Palindromic Subsequence in Python using Memoization

Longest Palindromic Subsequence in Python using Tabulation:

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:

Python

# 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(n²), where n is the length of the input string
Auxiliary Space: O(n²)

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.

Tags:

#python #DSA #Dynamic Programming #Strings #Dynamic Programming #python #Strings

Longest Palindromic Subsequence in Python using Tabulation:

Longest Palindromic Subsequence in Python using Memoization

Longest Palindromic Subsequence in Python

Similar Reads