Valid Parentheses

Stack
String

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.
Open brackets are closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.

Examples

Example 1

Input

s

(

)

[

]

{

}

Output

true

Example 2

Input

s

(

[

)

]

Output

false

Example 3

Input

s

(

Output

false

Constraints

1 ≤ s.length ≤ 10⁴
s consists of the characters '()[]{}' only.

Stuck? Hint 1

Push opening brackets, pop when a matching close arrives.

Editorial· A stack of open brackets

Read the string left to right, the way you'd check brackets in code by eye. An opening bracket is a promise: something later has to close it. A closing bracket keeps a promise, but not just any of them. It has to close the newest opening bracket that's still open. In {[()]}, the ) must close the (, because the [ and { were opened before it and are still waiting outside it.

Time O(n)Space O(n)

The full walkthrough and code in five languages, free to read

Input

(

)

[

]

{

}

Expected Output

true

Ctrl / ⌘ + Enter

Valid Parentheses

Stack
String

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.
Open brackets are closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.

Examples

Example 1

Input

s

(

)

[

]

{

}

Output

true

Example 2

Input

s

(

[

)

]

Output

false

Example 3

Input

s

(

Output

false

Constraints

1 ≤ s.length ≤ 10⁴
s consists of the characters '()[]{}' only.

Stuck? Hint 1

Push opening brackets, pop when a matching close arrives.

Editorial· A stack of open brackets

Read the string left to right, the way you'd check brackets in code by eye. An opening bracket is a promise: something later has to close it. A closing bracket keeps a promise, but not just any of them. It has to close the newest opening bracket that's still open. In {[()]}, the ) must close the (, because the [ and { were opened before it and are still waiting outside it.

Time O(n)Space O(n)

The full walkthrough and code in five languages, free to read

Input

(

)

[

]

{

}

Expected Output

true

Ctrl / ⌘ + Enter