noodleProblems/
Valid Parentheses
#30

Valid Parentheses

AlgorithmeasyStringStack

Given a string s containing only the bracket characters '(', ')', '{', '}', '[' and ']', decide whether it is *valid*.

A string is valid when:

- every opening bracket is closed by a matching bracket of the same type, and - brackets close in the correct order (the most recently opened bracket must be the first to close).

Return true if s is valid and false otherwise. The empty string is valid.

Example cases

  • single pair
    in s = "()"
    out true
    One opening bracket closed by its match.
  • mixed types
    in s = "()[]{}"
    out true
    Three independent matched pairs in sequence.
  • mismatch
    in s = "(]"
    out false
    '(' is closed by ']', which is the wrong type.
  • wrong order
    in s = "([)]"
    out false
    The '(' is closed before the inner '[', so the nesting order is broken.

Constraints

  • 1 <= s.length <= 10^4
  • s consists only of the characters '()[]{}'.
Saved
s =
"()"