Valid Brackets
Given an input string that contains brackets, write a function hasValidBrackets that returns a boolean indicating whether the brackets are valid.
- The brackets we will consider are
(,),[,],{,}. - The string can contain other characters, but those can be ignored.
- A string is valid if there are an equal number of opening brackets and closing brackets of the same type with all being matched.
- Brackets are considered matched if they appear in the correct order (must be opened before they are closed) and don't overlap.
Breakdown
Approach and test strategy
Last-in-first-out matching of a fixed delimiter alphabet
Read the approach, boundary cases, and complexity
Scan the string, pushing opening ASCII delimiters and matching each closing delimiter against the latest unmatched opener. Reject a close when the stack is empty or the delimiter types differ. Ordinary text is ignored under this lesson's contract. A final nonempty stack means an opener was never closed; equal counts alone cannot establish correct nesting.
Cases to check
- Empty input is valid; a lone opener or closer is not.
- The sequence ([)] is invalid despite matching delimiter counts.
- Mix ordinary text with nested brackets and include a delimiter next to a combining mark in languages whose string iteration uses grapheme clusters.
Cost model
One scan takes O(n) time in the chosen text representation. Up to O(n) unmatched opening delimiters may be retained. Be explicit about whether iteration visits bytes, UTF-16 units, Unicode scalars, or grapheme clusters.
Programming languages for this lesson
Starter code and reference implementations are available in:
The editor shows which of these languages can run on this deployment.
Validate My Answer
Every opening bracket must have a closing bracket AND they must be ordered correctly to be valid.
Think about solving this from the inside-out. For the brackets to be valid, you can start with the innermost open/close pair and compare those. If those match, you would set them aside and check the pairs after it. You really just need to be validating one potential match at a time.
With an additional data structure, you can solve this in O(n) time and space and only iterate through the string once.
Valid Brackets
Given an input string that contains brackets, write a function hasValidBrackets that returns a boolean indicating whether the brackets are valid.
- The brackets we will consider are
(,),[,],{,}. - The string can contain other characters, but those can be ignored.
- A string is valid if there are an equal number of opening brackets and closing brackets of the same type with all being matched.
- Brackets are considered matched if they appear in the correct order (must be opened before they are closed) and don't overlap.