Valid Parentheses

The problem

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

Function: def isValid(s):

Example input (a JSON list of arguments): ["()[]{}"]
Expected output: true

Inputs satisfy the problem statement. Sequences contain at most 200 elements unless a smaller bound is stated. Use JSON values and the supplied function signature.

Hints

1. Push opening brackets and require each closer to match the latest opener.
2. Check the supplied examples, empty/boundary cases and the stated answer policy before optimizing.

Worked answer

Try it yourself first. When you are ready, open the answer below.

def isValid(s):
    stack=[]; close={')':'(',']':'[','}':'{'}
    for c in s:
        if c in close:
            if not stack or stack.pop()!=close[c]: return False
        else: stack.append(c)
    return not stack

Why it works

Push opening brackets and require each closer to match the latest opener. An early mismatch or any remaining opener makes the sequence invalid; input contains only bracket characters.

Complexity: O(n) time / O(n) space.

Time: O(n) time · Space: O(n) space