Beat 78.08% Three JAVA WAY compare


  • 0
    A

    At first, my way is this.

    int index = 0;
    public boolean isValidSerialization(String preorder) {
        String[] nodes = preorder.split(",");
        if(nodes[0].equals("#")){
            if(nodes.length == 1) 
                return true;
            else     
                return false;
        }
        
        Stack<String> s = new Stack<>();
        return helper(s, nodes);
    }
    public boolean helper(Stack<String> stack, String[] nodes){
        if(index >= nodes.length)
            return false;
        if(nodes[index].equals("#")){
            index++;
            return true;
        }
        stack.push(nodes[index++]);
        boolean left = helper(stack, nodes);
        if(!left)
            return false;
        boolean right = helper(stack, nodes);
        if(!right)
            return false;
        stack.pop();
        if(stack.empty() && index < nodes.length)
            return false;
        return true;
    }
    

    After I see the top solution "7 lines Easy Java Solution": https://discuss.leetcode.com/topic/35976/7-lines-easy-java-solution

    I optimize my solution to get(using size instead of stack)

    int index = 0, size = 0;
    public boolean isValidSerialization(String preorder) {
        String[] nodes = preorder.split(",");
        if(nodes[0].equals("#")){
            if(nodes.length == 1) 
                return true;
            else     
                return false;
        }
        return helper(nodes);
    }
    public boolean helper(String[] nodes){
        if(index >= nodes.length)
            return false;
        if(nodes[index++].equals("#")){
    
            return true;
        }
        size++;
        if(!helper(nodes))//left case
            return false;
        if(!helper(nodes))//right case
            return false;
        //if both left and right is true. size--
        size--;
        if(size == 0 && index < nodes.length)
            return false;
        return true;
    }
    

    Final beat 78.08%!


Log in to reply
 

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