Valid Parentheses

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.

Constraints:

• 1 <= s.length <= 104
• s consists of parentheses: only ’()[]{}’.

The approach is clear straightforward: go through the string from left to right, making sure that all of the conditions are satisfied as we do so. The tricky part is how we make sure they are satisfied.

Notice that all of the conditions have to be satisfied as pairs.

• When we encounter an open bracket, we must make sure there is a corresponding closed bracket in the future.
• When we encounter a closed bracket, we have to make sure that the last bracket still in consideration matches is open and matches the type. What do we mean by still in consideration? For example, we have the string ”([])”. When we reach ”]”, we look for the last open bracket to be ”[”, which it is, and thus can close that pair of brackets. Effectively, we can ignore the substring ”[]”: on the next iteration, we look for the last open bracket which is ”(”, and thus can close that pair off as well.

This behaviour is last in, first out: the last open bracket considered is the first to be discarded. A stack is the perfect tool for the job.

def isValid(s: str) -> bool:
    stack = []

    for char in s:
        if char is an open bracket:
            add char to the stack
        if char is a closed bracket:
            if stack is empty: return False 

            pop the last open bracket off the stack
            if the last open bracket is not the same type:
                return False

    return whether stack is empty or not
    ...

There are two caveats that should be noted.

• What happens if the last condition is not fulfilled? Then there is a closed bracket that does not have a corresponding open bracket. This looks like reaching a closed bracket with an empty stack. As a result, we should return False when this occurs.
• What happens if there is an open bracket that is not closed at the end of the string? This looks like a non-empty stack at the end of the loop. We therefore have to check if the stack is empty or not at the end of the algorithm.

def isValid(self, s: str) -> bool:
    stack = []
    reverses = {
        "(": ")",
        "[": "]",
        "{": "}"
    }

    for char in s:
        if char in "([{":
            stack.append(reverses[char])
        elif char in ")]}":
            if len(stack) < 1:
                return False
            last = stack.pop()
            if last != char:
                return False

    return len(stack) == 0

Time Complexity

This algorithm has one loop of $n$ iterations, with each iteration taking constant time. Outside the loop, it only has constant time operations. Therefore, it is in $\mathcal{O}(n)$ time.

Space Complexity

In the worst case, the stack has $\frac{n}{2}$ elements inside. Other variables have constant space. Therefore, the algorithm uses $\mathcal{O}(n)$ space.