Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

 
public class Solution {
   public String longestPalindrome(String s) {
        if (s==null || s.length() <= 1) 
            return s; 
        
        int len = s.length(); 
        //record the length of longest palindrome
        int maxLen = 1; 
        //create a matrix to record the potential palindrome
        boolean[][]dp = new boolean[len][len];
        //return value
        String longest = null; 
        //check the input:
        for (int l = 0; l < len; l++) {
            //l: the half length of of substring we are checking 
            for (int i = 0; i < len-l; i++) {
                //i: left char index
                //j: right char index 
                int j = i+l; 
                //if they are equal, and their substring is also a palindrome
                if (s.charAt(i) == s.charAt(j) && (j-i<=2 || dp[i+1][j-1])){
                    dp[i][j] = true; 
                    if (j-i+1>maxLen) {
                        maxLen = j - i + 1; 
                        longest = s.substring(i, j+1);
                    }
                }
            }
        }
        return longest;
   }
}


Advertisements

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