Thursday, May 4, 2017

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.
Example:
Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.
Example:
Input: "cbbd"

Output: "bb"
Thoughts:

1. Brute Force
 It is the possibility of exhausting all the substrings, and then step by step to determine whether it is a palindrome and update the results. Although its time complexity is high, but its space requirements are very low.

public class Solution {
    public String longestPalindrome(String s) {
        int maxLength = 0;
        int maxStart = 0;
        int len = s.length();
        for(int i = 0; i < len; i++){
            //i is the length of s
            for(int j = 0; j < len - i; j++){
                //j is the start position
                if(isPalindrome(s, i , j) && (i + 1) > maxLength){
                    maxLength = i + 1;
                    maxStart = j;
                }
            }
        }
        return s.substring(maxStart, maxStart + maxLength);
    }
    private boolean isPalindrome(String s, int i, int j){
        int left = j;
        int right = j + i;
        while(left < right){
            if(s.charAt(left) != s.charAt(right)){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}
2. Dynamic Programming
According to the characteristics of the palindrome, a large palette after the proportion of the string must also be a palindrome, such as ABCCBA, that BCCB is also a palindrome. So we can according to the two characteristics of dynamic programming: the first big problem dismantling for small problems, the second repeated use of the previous calculation results, to answer this question. How can we divide the small problem, we can first all the shortest length of 1 sub-string calculated, according to the starting position from left to right, these must be palindrome. And then calculate all the length of 2 sub-string, and then according to the starting position from left to right. To the length of 3, we can use the results of the last calculation: If the center of the short string is not a palindrome, that long string is not, if the short string is palindrome, it depends on the long string Whether the two are the same. In this way, until the longest sub-string, we put the entire string set exhaustive, but due to the use of dynamic programming, so that the calculation time from O (N ^ 3) reduced to O (n ^ 2).

public class Solution {
    public String longestPalindrome(String s) {
        int maxLength = 0;
        int maxStart = 0;
        int len = s.length();
        boolean[][] dp = new boolean[len][len];
        for(int i = 0; i < len; i++){
            //i is the length of s
            for(int j = 0; j < len - i; j++){
                //j is the start position
                if(i == 0 || i == 1){
                    dp[j][j + i] = true;
                    //if start == end check center
                }else if(s.charAt(j + i) == s.charAt(j)){
                    dp[j][j + i] = dp[j + 1][j + i - 1];
                }else{
                    dp[j][j + i] = false;
                }
                if(dp[j][j + i] && i + 1 > maxLength){
                    maxLength = i + 1;
                    maxStart = j;
                }
            }
        }
        return s.substring(maxStart, maxStart + maxLength);
    }
 
}

No comments:

Post a Comment