# 每日一题（5）：最长回文子串
# 开始
看到这道题，首先就想到一件事很麻烦
既要支持"aba"，又要支持"abba"
殊不知这是完全两种不同的玩法
不过，在计算机领域，没有什么是不能通过抽象出一层来解决的
本着这个理念，我们不妨假设left指针和right指针
"aba"时，left和right只是同时指向"b"
"abba"时，left指向左边的"b"，right指针指向右边的"b"
这样我们就统一了处理逻辑
来看一下代码实现
class Solution {
char[] cs;
public String longestPalindrome(String s) {
cs = s.toCharArray();
String currKing = "";
for (int i = 0; i < cs.length; i++) {
String r = findByOdd(i);
if (i + 1 < cs.length && cs[i] == cs[i + 1]) {
r = getKing(r, findByEven(i));
}
currKing = getKing(currKing, r);
}
return currKing;
}
private String getKing(String s1, String s2) {
return s1.length() >= s2.length() ? s1 : s2;
}
private String findByEven(int mid) {
return find(mid, false);
}
private String findByOdd(int mid) {
return find(mid, true);
}
private String find(int mid, boolean isOdd) {
int left; int right;
if (isOdd) {
left = mid; right = mid;
} else {
left = mid; right = mid + 1;
}
boolean updated = false;
while (insideLeft(left) && insideRight(right)) {
if (cs[left] != cs[right]) {
break;
}
left--; right++;
updated = true;
}
if (updated) {
left++; right--;
}
return new String(cs, left, right - left + 1);
}
private boolean insideLeft(int i) {
return i > -1;
}
private boolean insideRight(int i) {
return i < cs.length;
}
}
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
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
其实写代码就是抽象的艺术
难点在于如何把一个复杂问题转化简单问题，并分而治之
这样代码便可以写得简洁美观
findByEven和findByOdd分别对应了处理"abba"和"aba"的逻辑
并且用left和right指针在find中实现实现了统一化处理
insideLeft和insideRight就可以知道是否越界，能否继续处理
getKing不说了，都懂
最后秀一下效率
欸嘿