LeetCode #20 Valid Parentheses

Easy

Problem

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:

Input: "()"
Output: true

Example 2:

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

Example 3:

Input: "(]"
Output: false

Example 4:

Input: "([)]"
Output: false

Example 5:

Input: "{[]}"
Output: true

Solution

This problem is a classic stack problem which is written on text book. Push the open bracket into stack and pop when meet a close one. It’s noted that stack should be empty after iterations or it’s still invalid.

Complexity

It’s trivial that time complexity is O(n) if n denotes to length of string because we only traverse entire string once. And it only uses O(1) extra space.