Codility Brackets 挑战性能问题

Question

尝试一个简单的 codility 挑战（检查一串 {} 字符是否格式正确）我被我的解决方案的性能得分很低甚至在他们的一些测试用例上超时的事实迷住了.

规格为"return 1 if well-formed, 0 otherwise":

class Solution {
public int solution(String S) {

    Deque<String> stack = new LinkedList<String>();
    while (S.length() > 0) {
        String firstChar = S.substring(0, 1);
        if (isOpenBracket(firstChar)) {
            stack.addFirst(firstChar);
        }
        else {
            String matchingOpen = closedToOpen(firstChar);
            if (matchingOpen == null) return 0;

            String topOfStack = stack.pollFirst();
            if (!matchingOpen.equals(topOfStack)) {
                return 0;
            }
        }
        S = S.substring(1);
    }
    return stack.isEmpty() ? 1 : 0;
}

public boolean isOpenBracket(String s) {
    return ("{".equals(s) || "[".equals(s) || "(".equals(s));
}

public String closedToOpen(String closed) {
    if ("}".equals(closed)) return "{";
    if ("]".equals(closed)) return "[";
    if (")".equals(closed)) return "(";
    return null;
}
}

起初我认为罪魁祸首是 addFirst / pollFirst 实际上附加在链表的远端，但事实并非如此（更改为 add/pollLast 实际上会产生相同的分数配置文件）。

我可以看到使用字符而不是字符串会加快速度，但我认为它的相关性不足以使测试超时（预期时间 <3 秒，运行时间 > 8 秒）...

我最后的猜测是 helpers 方法会在每次调用时重新分配常量...但是，这仍然有这么大的影响吗？

有什么想法吗？

Answer 1

问题在于，在长度为 n 的字符串上调用的子字符串的成本为 O(n)，因为它会进行复制。您想保留一个字符串并访问每个字符，而不是不断地复制字符串。

Codility Brackets 挑战性能问题

Codility Brackets challenge performance issue

java

algorithm

performance

implementation