Valid Parentheses

Easy·Tagsstringstack

Problem Statement

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.

Examples

Example 1

Input

s: "()"

Output

"true"

Why

The parentheses are correctly paired.

Example 2

Input

s: "()[]{}"

Output

"true"

Why

All brackets are correctly paired in sequence.

Example 3

Input

s: "(]"

Output

"false"

Why

The open parenthesis '(' is closed by a square bracket ']', which is invalid.

Example 4

Input

s: "([)]"

Output

"false"

Why

The square bracket ']' closes before the inner parenthesis ')' is closed.

Example 5

Input

s: "{[]}"

Output

"true"

Why

The inner square brackets are closed before the outer curly braces, which is valid.

Constraints

•1 <= s.length <= 10000
•s consists of parentheses only '()[]{}'.

Hints

Stuck? Reveal a nudge toward the right pattern, one step at a time.

Hint 1

You need to process the string from left to right. When you encounter a closing bracket, it must correspond to the *most recently seen* unmatched opening bracket.

Hint 2

Which data structure excels at accessing the 'most recently added' element? A Last-In-First-Out (LIFO) structure like a Stack!

Hint 3

Whenever you see an opening bracket, push it onto the stack. Whenever you see a closing bracket, pop the top element from the stack and check if they match.

Hint 4

If the stack is empty when you see a closing bracket, or if the popped element doesn't match, the string is invalid.