在做最长回文子字符串的问题(第 5 题)的时候, 我用的是 Manacher 算法,按理说应该可以过( O ( n )),但是居然超时了,答案倒是对的, 看了半天也不知道哪里出了问题,求助啊 T^T 。
下面是代码:
public class Solution {
public String longestPalindrome(String s) {
if (s.length() <= 1) {
return s;
}
String newString = addHelperChar(s);
int[] p = new int[newString.length()];
int maxId = 0;
int maxRange = 0;
for (int i = 1; i < newString.length(); i ++) {
p[i] = maxRange > i ? (p[2 * maxId - i] < maxRange - i ? p[2 * maxId - i] : maxRange - i) : 1;
while (i - p[i] > 0
&& i + p[i] < newString.length()
&& newString.charAt(i + p[i]) == newString.charAt(i - p[i])) {
p[i]++;
}
if (maxRange < p[i]) {
maxId = i;
maxRange = p[i];
}
}
String result = "";
for (int i = maxId - maxRange + 1; i < maxId + maxRange; i ++) {
char temp = newString.charAt(i);
if (temp != '#') {
result += temp;
}
}
return result;
}
public String addHelperChar(String s) {
String result = "$";
for (int i = 0; i < s.length(); i ++) {
result += "#";
result += s.charAt(i);
}
result += "#%";
return result;
}
}
1
ddmad1030 OP 刚刚在 lintcode 那边 submit 了同样的 code , 然后就 ac 了。。。
|
2
sleeperqp 2016-03-17 17:53:09 +08:00 1
public String addHelperChar(String s) {
String result = "$"; for (int i = 0; i < s.length(); i ++) { result += "#"; result += s.charAt(i); } result += "#%"; return result; } 感觉是这里的问题 string 的+=的效率问题 |
4
ddmad1030 OP @sleeperqp 感谢!听了你的意见,把 2 处用 string 直接加的地方全都换成 char[] 然后就通过了!
|
5
ddmad1030 OP @bdbai 感谢! 我改成用 char[] 运算就通过了,不过 stringbuilder 没有试,估计应该也可以的。
还是大意了,平时一直都是+= 这样也没出现什么问题,以后得注意了 |
6
bdbai 2016-03-17 20:09:49 +08:00 via iPhone 1
@ddmad1030 StringBuilder 就是专门用来处理字符串拼接的,用起来也很方便,推荐试一下。
|
7
roychan 2016-03-17 20:19:45 +08:00
好像 += 确实可能有效率问题
|
8
monkeylyf 2016-03-18 10:39:40 +08:00
跑个题 面试的时候你能记住 Manacher 吗 我觉得我的记忆里越来越差了
|