Longest Palindrome Subsequence

Given a sequence, find the length of the longest palindromic subsequence in it. For example, if the given sequence is “BBABCBCAB”, then the output should be 7 as “BABCBAB” is the longest palindromic subseuqnce in it. “BBBBB” and “BBCBB” are also palindromic subsequences of the given sequence, but not the longest ones.

 

// Everay single character is a palindrom of length 1
L(i, i) = 1 for all indexes i in given sequence

// IF first and last characters are not same
If (X[i] != X[j])  L(i, j) =  max{L(i + 1, j),L(i, j - 1)} 

// If there are only 2 characters and both are same
Else if (j == i + 1) L(i, j) = 2  

// If there are more than two characters, and first and last 
// characters are same
Else L(i, j) =  L(i + 1, j - 1) + 2 

 

Solution 1:

递归。

public int lps_recursive(String s) {
	return lps(s, 0, s.length()-1);
}

private int lps(String s, int i, int j) {
	if(i > j) return 0;
	if(i == j) return 1;
	if(s.charAt(i) == s.charAt(j)) {
		return lps(s, i+1, j-1) + 2;
	} else {
		return Math.max(lps(s, i+1, j), lps(s, i, j-1));
	}
}

 

Solution 2:

动态规划。

public int lps(String s) {
	int n = s.length();
	// f[i][j]: longest panlindrome seq from i to j
	int[][] f = new int[n][n];
	for(int i=0; i<n; i++) {
		f[i][i] = 1;
	}
	// sliding window size
	for(int w=2; w<=n; w++) {
		for(int i=0; i<=n-w; i++) {
			int j = i+w-1;
			if(s.charAt(i) == s.charAt(j)) {
				f[i][j] = (i+1>j-1?0:f[i+1][j-1]) + 2;
			} else {
				f[i][j] = Math.max(f[i+1][j], f[i][j-1]);
			}
		}
	}
	return f[0][n-1];
}