LeetCode5-最长回文子串

题目描述

给定一个字符串 s，找到 s 中最长的回文子串。

中心扩展法

可能是大部分人最先想到的思路。

思路：
遍历：从中心向外扩展，得出回文串长度，取最长的。
时间复杂度:
最坏情况下(比如相同字符构成的串:aaaa),内层循环会向外判断到最近的边界，
2*(1+2+3+···+n/2+···+3+2+1)
= 2*[2*(((n-1)/2)*((n+1)/2)/2)+n/2]
= (n^2+2n-1)/2
=> O(n^2)
注意点：
要分为奇偶数的回文串讨论
比如： abcaacdc
如果以一个字符为中心，得到的最长回文是 cdc，但是这明显不是最长的
如果以两个字符为中心，得到的最长回文是 caac，这才是正解。

我的实现:

public String longestPalindrome(String s) {
        int len  = s.length();
        if(len<2)return s;
        char [] c = s.toCharArray();
        int begin = 0;//起始下标
        int max = 1;//回文串长度

        //注意：len-i-1>=max/2。表示如果余下为遍历的位数(len-i-1)不足max的一半时就
        // 断定不会有更长回文串。
        for(int i = 0;i<len&&len-i-1>=max/2;i++){
            //奇数长度回文串判断
            for(int j=1;i-j>=0 && i+j<len;j++){
                if(c[i-j]==c[i+j]){
                    if(2*j+1>max){
                        begin = i-j;
                        max = 2*j+1;
                    }
                }else break;
            }
            //偶数长度回文串判断：
            for(int j=0;i-j>=0&&i+j+1<len;j++){
                if(c[i-j]==c[i+j+1]){
                    if(2*j+2>max){
                        begin = i-j;
                        max = j*2+2;
                    }
                }else break;
            }
        }
        return s.substring(begin,max+begin);
 }

看了下官方的实现：

public String longestPalindrome(String s) {
    if (s == null || s.length() < 1) return "";
    int start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
        int len1 = expandAroundCenter(s, i, i);
        int len2 = expandAroundCenter(s, i, i + 1);
        int len = Math.max(len1, len2);
        if (len > end - start) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    return s.substring(start, end + 1);
}

private int expandAroundCenter(String s, int left, int right) {
    int L = left, R = right;
    while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
        L--;
        R++;
    }
    return R - L - 1;
}

把扩展步骤独立出来了，更好理解。

动态规划

manacher算法

最优解