05 August 2008
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
1
2
3
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:
1
2
Input: "cbbd"
Output: "bb"
找最长回文子串，给定的字符串最长为1000，1)
1）首先可以O(n^2)，以每个字符为中心然后向两边延伸来检查，保留一个最长的子串即可，这个需要注意一下奇偶（以自己为中心以及以自己旁边的两个字符为中心）；
2）用dp，维护一个二维dp，其中dp[i][j]表示字符串区间[i, j]是否为回文串，当i==j时，只有一个字符，肯定是回文串；如果i = j + 1，那二者是相邻字符，此时判断s[i]是否等于s[j]即可；如果i和j不相邻，也就是i - j >= 2的时候，除了判断s[i]和s[j]相等，还得保证dp[j+1][i-1]也得为真，才是回文串，所以递推式为
dp[i, j] = 1 if i == j为回文串
1
2
3
= s\[i\] == s\[j\] if j = i + 1
= s\[i\] == s\[j\] && dp\[i + 1\]\[j - 1\] if j > i + 1
3）O(n)的马拉车算法Manacher’s Algorithm，O(n)时间，这里有详细介绍，这个看情况掌握。
O(n^2)
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
class Solution {
private int lo, maxLen;
public String longestPalindrome(String s) {
int len = s.length();
if (len < 2)
return s;
for (int i = 0; i < len - 1; i++) {
extendPalindrome(s, i, i); //assume odd length, try to extend Palindrome as possible
extendPalindrome(s, i, i + 1); //assume even length.
}
return s.substring(lo, lo + maxLen); // 这里为什么不是lo + maxLen + 1
}
private void extendPalindrome(String s, int left, int right) {//字符串和两个指针
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
//注意上面while循环是在左右不等才停止的，所以这里其实是如下所示，left和right都回退一步计算
if (maxLen < right - 1 - (left + 1) + 1) {
lo = left + 1;
maxLen = right - 1 - (left + 1) + 1;
}
}
}
DP，也是O(n ^ 2)
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
class Solution {
public String longestPalindrome(String s) {
int len = s.length();
int maxLen = 0;
boolean[][] dp = new boolean[len][len];
String result = "";
for (int left = len - 1; left >= 0; left--) { // left,right为区间[left, right]最长回文
for (int right = left; right < len; right++) {// right必须大于等于left，所以left从右到左，right从左到右比较好写
if (s.charAt(left) == s.charAt(right)) { // 两个字符相等
if (right - left <= 2) { //也就是子字符串长度是1/2/3的情况下，在left right字符相等的情况下总是true
dp[left][right] = true;
} else {
dp[left][right] = dp[left + 1][right - 1]; // left和right对应字符相等的情况下，取决与上一个状态
}
}
if (dp[left][right] && maxLen < right - left + 1) { // 计算当前dp对应的最长字符串
maxLen = right - left + 1;
result = s.substring(left, left + maxLen);
}
}
}
return result;
}
}
Manacher O(n)
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution {
public String longestPalindrome(String s) {
String manacherStr = preProcess(s);
int center = 0;
int radius = 0;
int[] manacherP = new int[manacherStr.length()];
for (int i = 1; i < manacherStr.length() - 1; i++) {
int iMirror = 2 * center - i;
if (iMirror >= 0 && iMirror < manacherStr.length()) {
manacherP[i] = radius > i ? Math.min(radius - i, manacherP[iMirror]) : 0;
}
int left = i - 1 - manacherP[i];
int right = i + 1 + manacherP[i];
while (manacherStr.charAt(left) == manacherStr.charAt(right)) {
left--;
right++;
manacherP[i]++;
if (left < 0 || right >= manacherStr.length()) {
break;
}
}
if (i + manacherP[i] > radius) {
center = i;
radius = i + manacherP[i];
}
}
int maxLen = 0;
int centerIndex = 0;
for (int i = 1; i < manacherStr.length() - 1; i++) {
if (manacherP[i] > maxLen) {
maxLen = manacherP[i];
centerIndex = i;
}
}
int start = (centerIndex - maxLen - 1) / 2;
int end = start + maxLen;
return s.substring(start, end);
}
private String preProcess(String s) {
if (s.length() == 0) {
return "^$";
}
StringBuilder sb = new StringBuilder("^");
for (int i = 0; i < s.length(); i++) {
sb.append("#").append(s.charAt(i));
}
sb.append("#$");
return sb.toString();
}
}