Longest Palindromic Subsequence

Thoughts:
Brute force solution, O(N^3):
The obvious brute force solution is to pick all possible starting and ending positions for a substring, and verify if it is a palindrome. There are a total of C(N, 2) such substrings (excluding the trivial solution where a character itself is a palindrome).

Since verifying each substring takes O(N) time, the run time complexity is O(N3).

Dynamic programming solution, O(N^2) time and O(N^2) space:
To improve over the brute force solution from a DP approach, first think how we can avoid unnecessary re-computation in validating palindromes.
Consider the case “ababa”. If we already knew that “bab” is a palindrome, it is obvious that “ababa” must be a palindrome since the two left and right end letters are the same.

Stated more formally below:

Define P[ i, j ] ← true iff the substring Si … Sj is a palindrome, otherwise false.

Therefore, P[ i, j ] ← ( P[ i+1, j-1 ] and Si = Sj )

The base cases are:
P[ i, i ] ← true
P[ i, i+1 ] ← ( Si = Si+1 )

This yields a straight forward DP solution, which we first initialize the one and two letters palindromes, and work our way up finding all three letters palindromes, and so on…

public static int lenOfMaxPalindrome(char[] a){
    public static int lenOfMaxPalindrome(char[] a){
    int n = a.length;
    int[][] table = new int[n][n];
    
    for(int i=0; i<n; i++){
        table[i][i] = 1; //when len=1
    }
    
    //len is length of substring
    for(int len=2; len<=n; len++){
        //the start position of substring
        for(int i=0; i<=n-len; i++){
            int j = i+len-1;//the end position of substring
            if(a[i] == a[j]){
                if(len == 2){
                    table[i][j] = 2;
                }else{
                    table[i][j] = table[i+1][j-1] + 2; //the element on down-left
                }
            }else{
                table[i][j] = max(table[i][j-1], table[i+1][j]);
            }   
        }
    }
    
    return table[0][n-1];
}

public static int max(int i, int j){
    return i>j? i: j;
}

Time Complexity: O(n^2)

For example:
String is “abacba”





References:
http://www.geeksforgeeks.org/archives/19155
http://www.leetcode.com/2011/11/longest-palindromic-substring-part-i.html

Advertisements

About chesterli0130

Think more
This entry was posted in Uncategorized. Bookmark the permalink.

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 )

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