Why is my JAVA solution so slow?


  • 0
    L

    Code below.

        public boolean isValidSerialization(String preorder) {
            if (preorder == null || preorder.length() == 0 || preorder.trim().equals("#")) {
                return true;// Here we consider {"#"} as invalid.
            }
            int counter = 1;// Abstract of a stack.
            
            String[] nodes = preorder.trim().split("(\\s*)(,){1}(\\s*)");// Split and trim.
            for (int i = 0; i < nodes.length; i++) {
                if (nodes[i].trim().equals("#")) {
                    counter--;
                } else {
                    counter++;
                }
                if (counter < 0 || counter == 0 && i < nodes.length - 1) {// Too many leaves || build tree under a leaf.
                    return false;
                }
            }
            
            if (counter == 0) {
                return true;
            } else {
                return false;
            }
        }
    

    Some explanation: We treat null as a leaf of tree => Root provides 2 possible nulls, other nodes provide 1 null each. => We count whether leaves have outnumbered our expectation.

    The code traversed the array only once with only comparison operations, self add/sub, but it only beats 4%. Which part took so long? There are two performance peaks in the chart, meaning two better solutions (9ms, 20ms), what are they?

    Thanks!


  • 0

    Because you're splitting with a rather complicated regular expression. Just split on "," and your time will drop to a third.


  • 0
    L

    Indeed. Never noticed regex could have such impact on performance. Thanks, Stefan.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.