Source URL: https://leetcode.com/problems/valid-parentheses/

Given a string containing just the characters `'('`

, `')'`

, `'{'`

, `'}'`

, `'['`

and `']'`

, determine if the input string is valid.

An input string is valid if:

- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

**Example 1:**

Input:"()"Output:true

**Example 2:**

Input:"()[]{}"Output:true

**Example 3:**

Input:"(]"Output:false

**Example 4:**

Input:"([)]"Output:false

**Example 5:**

Input:"{[]}"Output:true

This is a textbook usage of the stack. The stack is born to solve nest structures. Every time we meet a “(“, “[” or “{“, we push it to the top of the stack, and every time we meet a “)”, “]” or “}”, we pop the top of the stack. And we compare the current close bracket with the open bracket popped up. If they are matched, we know it is valid.

This is the code, my stack:

Push open bracket, meet close bracket pop, and compare them:

Running time 1ms, faster than *98.28%* java submission。

Github：https://github.com/tinyfool/leetcode/tree/master/src/p0020

Other problems related to stack and queue, see also Stack and Queue Data Structure (Java code and Leetcode problems)