Longest palidromic subsequence
Longest Palindromic Subsequence is the problem of finding the longest palindromic subsequence of a sequence.
The solution utilizes dynamic programming.
The problem is usually defined as:
Given a sequence of items, find the length of the longest subsequence which is a palindrome. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. For example, in the string abcdefg, "abc", "abg", "bdf", "aeg" are all subsequences.
def lps_len(m, n,S): """This function returns length of longest palindromic sequence of x and y.""" if n==m: return 1 if S[m]==S[n] and m+1==n: return 2 if S[m]==S[n]: return lps(m+1,n-1,S)+2 else: return max(lps(m+1,n,S),lps(m,n-1,S)
def lps(S): n = len(S) LPS=[*n]*n for i in range(n): LPS[i][i]=1 for i in range(n-1,-1,-1): for j in range(i+1,n): if S[i]==S[j]: LPS[i][j]=2+LPS[i+1][j-1] else: LPS[i][j]=max(LPS[i+1][j],LPS[i][j-1]) return LPS[n-1]