This can be solved in O(n^2) using dynamic programming. Basically, the problem is about building the longest palindromic subsequence in x[i...j]
using the longest subsequence for x[i+1...j]
, x[i,...j-1]
and x[i+1,...,j-1]
(if first and last letters are the same).
Firstly, the empty string and a single character string is trivially a palindrome.
Notice that for a substring x[i,...,j]
, if x[i]==x[j]
, we can say that the length of the longest palindrome is the longest palindrome over x[i+1,...,j-1]+2
. If they don't match, the longest palindrome is the maximum of that of x[i+1,...,j]
and y[i,...,j-1]
.
This gives us the function:
longest(i,j)= j-i+1 if j-i<=0,
2+longest(i+1,j-1) if x[i]==x[j]
max(longest(i+1,j),longest(i,j-1)) otherwise
You can simply implement a memoized version of that function, or code a table of longest[i][j] bottom up.
This gives you only the length of the longest subsequence, not the actual subsequence itself. But it can easily be extended to do that as well.
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…