life is fun, programming

Longest Palindrom Subsequence via Dynamic Programming


/**
* @author Victor Fang, 20140728
* finding longest palindrom subsequence.
* there can be extra letters within.
* example: BBABCBCAB has 7 char palindrom: babcbcb
*
* Dynamic Programming solution via Recursion:
* input X[]
* interim: L[i,j] = length of longest palindrom between i,j
* Base 1:
* L[i,i] = 1;
*
* Base 2:
* L[i, i+1] = 2;
*
* Recursion:
* if( X[i] == X[j] ) { L[i,j] = 2 + L[i+1, j-1] }
*
* if( X[i] != X[j] ) { L[i,j] = max(L[i+1, j], L[i, j-1]) }
*
*/
public class PalindromDP {
public static int max(int a, int b){ return (a>b)?a:b; }

public static int lps(char x[], int i, int j){

// base 1: lps[]
if(i == j) return 1;
if((j == i+1) && (x[i] == x[j])) return 2;

if( x[i] == x[j]) {
return( 2 + lps(x, i+1, j-1) ) ;
}
if( x[i] != x[j]) {
return( max(lps(x, i+1, j) , lps(x, i, j-1)) );
}
return 0;

}

public static void main(String[] args) {

String x = “abigailfang”;
//String x = “BBABCBCAB”;
System.out.println(x);
System.out.println(lps(x.toCharArray(), 0, x.length()-1));
}

}

 

Standard

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s