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.

方法 1：动态规划

  1. state: dp[i][j] means if substring from i to j is palindromic or not
  2. init:
  3. function: dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])
  4. result:

时间复杂度 O($n^2$) 空间复杂度 O($n^2$)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public String longestPalindrome(String s) {
    if (s == null || s.length() == 0)
        return "";
    int n = s.length();
    boolean[][] dp = new boolean[n][n];
    String res = "";
    int max = 0;
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            if (s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])) {
                dp[i][j] = true;
                if (max < j - i + 1) {
                    max = j - i + 1;
                    res = s.substring(i, j + 1);
                }
            }
        }
    }
    return res;
}

方法 2:

基本思路是对于每个子串的中心（可以是一个字符，或者是两个字符的间隙，比如串abc,中心可以是a,b,c,或者是ab的间隙，bc的间隙）往两边同时进行扫描，直到不是回文串为止。假设字符串的长度为n,那么中心的个数为2*n-1(字符作为中心有n个，间隙有n-1个）。对于每个中心往两边扫描的复杂度为O(n),所以时间复杂度为O($n^2$),空间复杂度为O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public String longestPalindrome(String s) {
    if (s == null || s.length() == 0) {
        return "";
    }
    int length = s.length();    
    int max = 0;
    String result = "";
    for(int i = 1; i <= 2 * length - 1; i++){
        int count = 1;
        while(i - count >= 0 && i + count <= 2 * length  && get(s, i - count) == get(s, i + count)){
            count++;
        }
        count--; // there will be one extra count for the outbound #
        if(count > max) {
            result = s.substring((i - count) / 2, (i + count) / 2);
            max = count;
        }
    }
    return result;
}
private char get(String s, int i) {
    if(i % 2 == 0)
        return '#';
    else
        return s.charAt(i / 2);
}

方法 3: Manacher

时间复杂度 O(n)