Problem: Valid Parentheses

Let’s look at a classic stack problem: checking whether a string of brackets is valid.

A string is valid when every opening bracket is closed by a bracket of the same type, and brackets are closed in the correct order.

You have seen this check already. The Java compiler does it on every file you compile. Every { must have a matching }, and every ( must have a matching ), and they have to nest properly. If they do not, you get a syntax error. Most programming languages have the same requirement, and many text editors check it as you type.

Here are some examples of strings that are valid:

• () — one pair.
• ()[]{} — three pairs, one after another.
• {[()]} — three pairs, nested inside each other.

And these are invalid:

• (] — the opening bracket is closed by a bracket of a different type.
• (() — the first bracket is never closed.
• )( — a closing bracket appears before its opening bracket.
• ([)] — the brackets close in the wrong order.

The signature of the method in Java might look like this:

public static boolean isValid(String s) {
  // Your implementation goes here
}

We can iterate over the characters of the string with s.charAt(i) and s.length().

This problem usually comes with a constraint: solve it in $O(n)$ time, where $n$ is the length of the string.

Let’s think of some special or edge cases as well:

• If the string is empty, there are no brackets to mismatch, so the method should return true.
• If the string has a single character, that bracket has no matching bracket, so the method should return false.
• More generally, a valid string must have an even length, because brackets come in pairs.
• If the first character is a closing bracket, the string is invalid, no matter what follows.

I suggest that you try the problem without a stack first, and test your idea on ([)].