「リートコード - 5. Longest Palindromic Substring」

ジャバソリューション

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
class Solution {
public String longestPalindrome(String s) {
int start = 0, end = -1;
StringBuffer t = new StringBuffer("#");
for (int i = 0; i < s.length(); ++i) {
t.append(s.charAt(i));
t.append('#');
}
String ns = t.toString();
int n = ns.length();
int[] p = new int[n];
int res = -1, pos = -1;
int right = -1, mid = -1;
for (int i = 0; i < n; ++i) {
p[i] = right > i ? Math.min(p[2 * mid - i], right - i) : 0;
while (i - p[i] - 1 >= 0 && i + p[i] + 1 < n && ns.charAt(i - p[i] - 1) == ns.charAt(i + p[i] + 1)) {
++p[i];
}
if (right < i + p[i]) {
right = i + p[i];
mid = i;
}
if (res < p[i]) {
res = p[i];
pos = i;
}
}
return s.substring((pos - res) / 2, (pos + res) / 2);
}
}

好吧,简单复习下马拉车。