v9.1.1
Menu

Valid Parentheses

easyFREEStrings & ParsingApple DSA

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

An input string is valid if:

  • Open brackets are closed by the same type of brackets
  • Open brackets are closed in the correct order

Example

Input
()[]{}
Output
True
Reasoning
  • The input s is a string of 6 bracket characters, ()[]{}, and the output is a single boolean saying whether every bracket is properly paired.
  • Reading left to right, characters 1 and 2 are ( then ): an opener immediately followed by a closer of the same type, so they form a matched pair.
  • The same happens for characters 3 and 4 ([ then ]) and characters 5 and 6 ({ then }). That gives 3 pairs covering all 6 characters.
  • The "correct order" rule means each closer must match the most recent opener that is still unclosed. Here that opener is always the character just before it, so the rule holds at every step and the answer is True.
  • Notice that type and order both matter: an opening round bracket followed by a closing square bracket is False, and interleaving two pairs (round open, square open, round close, square close) is also False even though the counts balance, while nesting one pair fully inside another is valid.

Constraints

  • 1 <= len(s) <= 10^4
  • s consists of parentheses only

More from Apple DSA

solution.py

Test results

Sign in to run your code against the test cases.