Valid Parentheses

Easy

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if open brackets are closed by the same type of brackets and in the correct order.

Constraints

1 ≤ s.length ≤ 10^5
s consists of brackets only

Examples

Input

s = "()"

Output

true

Explanation

The string contains one opening bracket ( followed by one closing bracket ). Since every opening bracket is properly closed in the correct order, the parentheses are balanced. So, the string is valid, and the output is true.

Input

s = "([)]"

Output

false

Explanation

The string has the brackets (, [, ), and ]. Although each type of bracket appears, they are not in the correct order. The opening ( should be closed by ) before closing [. But here, [ is opened and ) comes next, which breaks the proper nesting rule. Because the brackets are not properly nested, the string is invalid, so the output is false.

Hints

💡 Hint 1

💡 Hint 2

Code

Upload

Test Result

Run your code to see results here...