Java using 2 stacks. O(n) space and time complexity.


  • 11
    M

    The basic idea is to track the index of the left bracket and star position.
    Push all the indices of the star and left bracket to their stack respectively.
    STEP 1
    Once a right bracket comes, pop left bracket stack first if it is not empty. If the left bracket stack is empty, pop the star stack if it is not empty. A false return can be made provided that both stacks are empty.

    STEP 2
    Now attention is paid to the remaining stuff in these two stacks. Note that the left bracket CANNOT appear after the star as there is NO way to balance the bracket. In other words, whenever there is a left bracket index appears after the Last star, a false statement can be made. Otherwise, pop out each from the left bracket and star stack.

    STEP 3
    A correct sequence should have an empty left bracket stack. You don't need to take care of the star stack.

    Final Remarks:
    Greedy algorithm is used here. We always want to use left brackets to balance the right one first as the * symbol is a wild card. There is probably an O(1) space complexity but I think this is worth mentioning.

        public boolean checkValidString(String s) {
            Stack<Integer> leftID = new Stack<>();
            Stack<Integer> starID = new Stack<>();
            for (int i = 0; i < s.length(); i++) {
                char ch = s.charAt(i);
                if (ch == '(')
                    leftID.push(i);
                else if (ch == '*')
                    starID.push(i);
                else {
                    if (leftID.isEmpty() && starID.isEmpty())   return false;
                    if (!leftID.isEmpty())
                        leftID.pop();
                    else 
                        starID.pop();
                }
            }
            while (!leftID.isEmpty() && !starID.isEmpty()) {
                if (leftID.pop() > starID.pop()) 
                    return false;
            }
            return leftID.isEmpty();
        }
    

  • 0
    J

    @MichaelPhelps
    Cool solution!!


  • 0
    N

    @MichaelPhelps I am not sure i completely understand how you implement step 2 in the algorithm. how do you know in the end whether the asterisk was pushed in before or after the opening bracket since they are 2 different stacks for each?
    i suppose how do we solve for this case '***(((' this is an invalid string?


  • 0
    M

    @nl2017
    check the following code

        while (!leftID.isEmpty() && !starID.isEmpty()) {
            if (leftID.pop() > starID.pop()) 
                return false;
        }
    

    the starID stack has elements [0, 1, 2]
    the leftID stack has elements [3, 4, 5]

    Since neither of them is empty, you can pop a pair of the indices and compare which one is larger.
    In this case, 5 > 2 which means this is an invalid input as there is no way to balance the left bracket.

    Here is another example: *((** :
    the starID stack has elements [0, 3, 4]
    the leftID stack has elements [1, 2]
    When you pop the first pair 2 < 4, OK, continue
    when you pop the first pair 1 < 3, OK, continue again
    now you have nothing left in the leftID, that's a valid input.

    Hope this explanation helps.


  • 0
    N

    @MichaelPhelps , thanks much. not sure how i missed the fact that we are storing indices of the opening brackets and the asterisks in the stacks. great solutions btw.


Log in to reply
 

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