方法一 暴力法

由長到短遍歷所有子字符串, 若為回文字符串則返回
遍歷時間復雜度O(n^2), 判斷回文時間復雜度O(n),總時間復雜度為O(n^3)

class Solution {
    public String longestPalindrome(String s) {
        //從長到短截取所有子字符串
        String sub="";
        int count;
        boolean tag = false;
        for(int i = s.length(); i > 0; i--){    //i 子字符串長度
            for(int j = 0; j <= s.length() - i; j++){        //j 子字符串起始位置
                sub = s.substring(j, j + i);
                
                //判斷是否是回文
                count = 0;
                for(int k = 0; k < sub.length() / 2; k++){
                    if(sub.charAt(k) == sub.charAt(sub.length() - k - 1))
                        count++;
                }
                if(count == sub.length() / 2)
                    return sub;
            }
            if(tag)
                break;
        }
        return "";
    }
}

方法二 中心擴撒發(fā)

以給定的字符為中心,向兩邊擴散,尋找最長的回文字符串
很明顯要將回文子字符串長度分為偶數(shù)和奇數(shù)兩種情況

• 奇數(shù)(如 aba) 以i為中心擴散
• 偶數(shù)(如abba) 以i和i+1為中心擴散

時間復雜度:O(n^2)

public String longestPalindrome(String s) {
    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) {
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        left--;
        right++;
    }
    return right - left - 1;
}

方法三 動態(tài)規(guī)劃

回文字符串的子串也是一個回文, 這就是一個動態(tài)規(guī)劃問題,如我們已經(jīng)知道"aba"是一個回文,那么"cabac"也是一個回文

P(i, j) = true 表示字符串 S(i) 到 S(j)是一個回文
那么P(i, j) = (P(i+1, j-1) == true and S(i) == S(j))
初始條件:
　　　　P(i, i) = true
　　　　P(i, i+1) = true

時間復雜度: O(n^2)
空間復雜度: O(n^2)

class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        int maxLen = 0;
        int start = 0;
        boolean p[][] = new boolean[len][len];
        
        if(s.length != 0)
            maxLen = 1;
        
        //初始化p[i][i] 和 p[i][i+1]
        for(int i = 0; i < len; i++){
            p[i][i] = true;
            if(i < len -1 && s.charAt(i) == s.charAt(i+1)){
                p[i][i+1] = true;
                maxLen = 2;
                start = i;
            }
            
        }
        
        for(int strlen = 3; strlen <= len; strlen++){    //窗口大小3 ~ len-1
            for(int i = 0; i <= len-strlen; i++){       //滑動窗口起始位置
                int j = i + strlen -1;                  //結(jié)束位置
                if(p[i+1][j-1] && s.charAt(i) == s.charAt(j)){
                    p[i][j] = true;
                    maxLen = strlen;
                    start = i;
                }
            }
        }
        return s.substring(start, start+maxLen);
    }
}