Valid Parentheses

Easy · Stack

You are given a string containing only the characters (, ), {, }, [ and ]. Determine whether the brackets form a valid sequence. A sequence is valid if every closing bracket matches the most recently opened bracket of the same type, and every bracket that is opened is eventually closed in the correct order. Return true if the string is valid, false otherwise.

Examples

Input:  s = "()[]{}"
Output: true
Why:    Each opening bracket is closed immediately by the matching bracket type, so the whole string is balanced.

Input:  s = "(]"
Output: false
Why:    The closing bracket ] does not match the most recently opened bracket (.

Input:  s = "([)]"
Output: false
Why:    The brackets are interleaved incorrectly: ) closes before the [ that was opened after ( is closed.

Input:  s = "{[]}"
Output: true
Why:    The innermost [] closes correctly, then the outer {} closes correctly, so it is valid.

Constraints

1 <= s.length <= 10^4, s consists only of the characters '(', ')', '{', '}', '[' and ']'

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Valid Parentheses

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Valid Parentheses. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.