# Problem 20: Valid Parentheses

Given a string 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.

Note that an empty string is also considered valid.

Example 1:

Example 2:

Example 3:

Example 4:

Example 5:

# Good solution for efficiency

left and right are lists. mapping is a dictionary, which combines right and left using dict and zip function. Searching/matching in dictionary would be more efficient than in list.

Pythonic way to express checking:

If s[i] is not ‘)’,’}’,’]’, then stack.append(s[i]); if s[i] is ‘)’,’}’,’]’, then compare it with stack.pop() — the top element in stack. Concise code speeds the execution…

# My ugly solution

Too many “if” checks slow the solution.

This check above for test case without left brackets:

“]”

This check above for test case in disorder:

“(])”