Valid Parentheses

Problem

You are given a string s made up only of the six bracket characters (, ), [, ], {, }. Decide whether the string is well-formed: every opening bracket must be closed by a bracket of the same kind, and brackets must close in the reverse order they were opened (no interleaving like ([)]). The empty string counts as well-formed.

• The string can be empty and has at most 20,000 characters.
• No characters other than the six brackets appear.

Examples

• s = "{}[()]" → true. A pair of braces, then a pair of square brackets that wraps a pair of parentheses; everything closes in the right order.
• s = "{(})" → false. When } arrives the innermost open bracket is (, so the kinds do not match.
• s = "[[]" → false. The brackets that are closed are closed correctly, but one [ is never closed.

Hints

1. When you see a closing bracket, which opening bracket must it match: the first one you saw, or the most recent unmatched one?
2. "Most recent unmatched" is a last-in, first-out relationship.
3. Push openers onto a stack; on each closer, pop and check the kind matches. The string is valid only if the stack is empty at the end.