Home > life is fun, programming > Longest Palindrom Subsequence via Dynamic 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));
}

}

 

Advertisements
Categories: life is fun, programming
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: