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)