Please follow the format below to answer this problem! 2. A palindrome is any st
ID: 3870712 • Letter: P
Question
Please follow the format below to answer this problem!
2. A palindrome is any string that is exactly the same as its reversal, like I, or DEED, or RACECAR, or AMANAPLANACATACANALPANAMA. Describe and analyze an efficient algorithm to find the length of the longest palindrome subsequence of a given string/array A[1 .. n]. For example, the longest palindrome subsequence of MAHDYNAMICPROGRAMZLETMESHOWYOUTHEM is MHYMRORMYHM. Yes, the palindrome subsequence may have odd length. Your analysis should explain how much time and space your algorithm uses.Explanation / Answer
Recursive Solutions
Let X[0..n-1] be the input sequence of length n and L(0, n-1) be the length of the longest palindromic subsequence of X[0..n-1].
If last and first characters of X are same, then L(0, n-1) = L(1, n-2) + 2.
Else L(0, n-1) = MAX (L(1, n-1), L(0, n-2)).
Following is a general recursive solution with all cases handled
In the above partial recursion tree, L(1, 4) is being solved twice. If we draw the complete recursion tree, then we can see that there are many subproblems which are solved again and again.
Time Complexity will be O(2n).
We can have multi dimensional array.Recomputations of same subproblems can be avoided by constructing a temporary array L[][] in bottom up manner.
It can can in following way
int lps(char *str)
{
int n = strlen(str);
int i, j, cl;
int L[n][n]; // Create a table to store results of subproblems
for (i = 0; i < n; i++)
L[i][i] = 1;
for (cl=2; cl<=n; cl++)
{
for (i=0; i<n-cl+1; i++)
{
j = i+cl-1;
if (str[i] == str[j] && cl == 2)
L[i][j] = 2;
else if (str[i] == str[j])
L[i][j] = L[i+1][j-1] + 2;
else
L[i][j] = max(L[i][j-1], L[i+1][j]);
}
}
return L[0][n-1];
}