NeetCode 150: Valid Parentheses

Table of contents

The Problem

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

The Approach

The goal is to ensure every open bracket has a valid close bracket & no pair of brackets start with a close bracket.

We can use a Stack to keep track of the order of closure for each open bracket.

By the nature of a stack, a LIFO (last in, first out) data structure, it ensures that the latest open bracket added to the stack is closed first.

We add all open brackets to the stack, and if the current character is a close bracket, check that it is a matching pair to the open bracket at the top of the stack.

At the end of the loop, we ensure that all open brackets are closed successfully (i.e. the stack is empty).

My Solution

class Solution {
    String openBrackets = "([{";

    public boolean isValid(String s) {
        // LIFO Data Structure.
        Deque<Character> bracketsTracker = new ArrayDeque<Character>();

        for (int i = 0; i < s.length(); i++) {
            char currentChar = s.charAt(i);

            // If the currentChar is a open bracket, add this to bracketsTracker.
            if (openBrackets.indexOf(currentChar) != -1) {
                bracketsTracker.push(currentChar);
            // Else (currentChar is a close bracket), check that bracketsTracker is not empty.
            } else if (!(bracketsTracker.isEmpty())) {
                char bracketToBeClosed = bracketsTracker.peek();

                // Compare the currentChar to the bracket at the top of bracketsTracker (has to be closed first).
                boolean result = checkForCorrespondingBracket(currentChar, bracketToBeClosed);
                // If the pair is valid, remove the open bracket, otherwise return false.
                if (result) {
                    bracketsTracker.pop();
                } else {
                    return false;
                }
                
            // Scenario that a close bracket is added to an empty stack, which is invalid.
            } else {
                return false;
            }
        }
        // Final check for no "outstanding" brackets.
        return bracketsTracker.isEmpty();
    }

    // Checks if the the two brackets passed is a valid pair.
    private boolean checkForCorrespondingBracket(int first, int second) {
        int difference = Math.abs(first - second);
        return (difference <= 2);
    }
}

Firstly, we initialize bracketsTracker which is a Deque (which is an interface, Stack is a class).

We then loop over all the elements in s, pushing every open bracket to bracketsTracker. The moment the current character is a close bracket, we check that bracketsTracker is not empty (scenario if the close bracket came before open bracket) and peek the open bracket at the top of bracketsTracker.

We then check if currentChar (the current bracket) & bracketToBeClosed is a valid pair through checkForCorrespondingBracket().

Explanation on the helper function.

Image taken from CS50.

From the ASCII table, the difference between each character in a pair of brackers is less than 2 (only () has a difference of 1). By calculating this absolute difference of the int values of the arguments & checking if it is <=2, we can check if it is a valid set.

If it is a valid pair, the respective open bracket is removed. Else, it is an invalid pair & false is returned (s is invalid).

If the loop completes & bracketsTracker is empty, means s is valid.