Longest Palindromic Substring 200

Question

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.

Example

Given the string = "abcdzdcab", return "cdzdc".

Challenge

O(n2) time is acceptable. Can you do it in O(n) time.

Solution

三种方法。

第一种brute force，遍历每一个点i，同时遍历0-len的长度，并判断i－i＋l是否为palindromic。时间复杂度O(n^3)，完全不能接受。

第二种DP，思想为求i－j的substring是否为palindromic，只要判断i和j是否相同，同时i＋1～j－1是否为palindromic。因此右边界j每次向右移一位，左边界i每次从0-j。时间复杂度为O(n^2)。

第三种为中心展开，在字符串开头结尾和之间加上“＃”，然后遍历新字符串，求以当前字符为中心的最长palindromic字符串的长度。方法为从当前字符串出发，向左右两边延伸，每次延伸判断延伸的两端新字符是否相等，一直延伸到不能再延伸为止。记录最长的字符串即为答案。该方法时间复杂度依然是O(n^2)？

第三种方法的优化：http://blog.csdn.net/hopeztm/article/details/7932245。但是实现不出来。。。

代码如下：

public class Solution {
    /**
     * @param s input string
     * @return the longest palindromic substring
     */
     //O(n^3) BF
    // public String longestPalindrome(String s) {
    //     // Write your code here
    //     if(s == null || s.length() == 0){
    //         return "";
    //     }

    //     int len = s.length();
    //     int max = 0;
    //     int[] index = new int[2];
    //     for(int i = 0; i < len; i++){
    //         for(int l = 1; l <= len; l++){
    //             if(i + l <= len){
    //                 if(l > max && isPalindrome(s, i, i + l - 1)){
    //                     max = l;
    //                     index[0] = i;
    //                     index[1] = i + l;
    //                 }
    //             }else{
    //                 break;
    //             }
    //         }
    //     }

    //     return s.substring(index[0], index[1]);
    // }

    // private boolean isPalindrome(String s, int start, int end){
    //     while(start < end){
    //         if(s.charAt(start) != s.charAt(end)){
    //             return false;
    //         }
    //         start++;
    //         end--;
    //     }
    //     return true;
    // }

    //O(n^2) DP
    // public String longestPalindrome(String s) {
    //     // Write your code here
    //     if(s == null || s.length() == 0){
    //         return "";
    //     }

    //     int len = s.length();
    //     boolean[][] dp = new boolean[len][len];

    //     int max = 0;
    //     String sb = "";
    //     for(int j = 0; j < len; j++){
    //         for(int i = 0; i <= j; i++){
    //             if(s.charAt(i) == s.charAt(j)){
    //                 if(j - i <= 1 || dp[i + 1][j - 1]){
    //                     dp[i][j] = true;
    //                     if(j - i + 1 > max){
    //                         max = j - i + 1;
    //                         sb = s.substring(i, j + 1);
    //                     }
    //                 }
    //             }else{
    //                 dp[i][j] = false;
    //             }
    //         }
    //     }

    //     return sb;
    // }

    //O(n) 中心展开
    public String longestPalindrome(String s) {
        // Write your code here
        if(s == null || s.length() == 0){
            return "";
        }

        int len = s.length();
        int max = -1;
        String sb = "";
        for(int i = 1; i < 2 * len; i++){
            int count = 1;
            while(i - count >= 0 && i + count <= 2 * len && get(s, i - count) == get(s, i + count)){
                count++;
            }
            count--;
            if(count > max){
                max = count;
                sb = s.substring((i - count) / 2, (i + count) / 2);
            }
        }
        return sb;
    }

    private char get(String s, int index){
        if(index % 2 == 0){
            return '#';
        }else{
            return s.charAt(index / 2);
        }
    }
}