Leetcode 刷题遇到的问题！求助！

请不要在回答技术问题时复制粘贴 AI 生成的内容

This topic created in 3729 days ago, the information mentioned may be changed or developed.

在做最长回文子字符串的问题（第 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; } }

9 repies 2016-03-18 11:25:33 +08:00

ddmad1030

Mar 17, 2016

刚刚在 lintcode 那边 submit 了同样的 code ，然后就 ac 了。。。

sleeperqp

Mar 17, 2016

public String addHelperChar(String s) {
String result = "$";

for (int i = 0; i < s.length(); i ++) {
result += "#";
result += s.charAt(i);
}

result += "#%";

return result;
}
感觉是这里的问题 string 的+=的效率问题

bdbai

Mar 17, 2016 via iPhone

@sleeperqp 试下用 StringBuilder

ddmad1030

Mar 17, 2016

@sleeperqp 感谢！听了你的意见，把 2 处用 string 直接加的地方全都换成 char[] 然后就通过了！

ddmad1030

Mar 17, 2016

@bdbai 感谢！我改成用 char[] 运算就通过了，不过 stringbuilder 没有试，估计应该也可以的。
还是大意了，平时一直都是+= 这样也没出现什么问题，以后得注意了

bdbai

Mar 17, 2016 via iPhone

@ddmad1030 StringBuilder 就是专门用来处理字符串拼接的，用起来也很方便，推荐试一下。

roychan

Mar 17, 2016

好像 += 确实可能有效率问题

monkeylyf

Mar 18, 2016

跑个题面试的时候你能记住 Manacher 吗我觉得我的记忆里越来越差了

ddmad1030

Mar 18, 2016

@monkeylyf 面试不复习的话应该也是记不住的因为平时写 code 根本用不到。。。