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

[ddmad1030]

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

[ddmad1030]

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

[sleeperqp]

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]

@sleeperqp 试下用 StringBuilder

[ddmad1030]

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

[ddmad1030]

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

[bdbai]

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

[roychan]

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

[monkeylyf]

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

[ddmad1030]

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