Interview Question
Share Lesson

# 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

Share:

1. Every opening bracket must have a closing bracket AND they must be ordered correctly to be valid.

2. 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.

3. With an additional data structure, you can solve this in O(n) time and space and only iterate through the string once.

Share:

Test Results

Run your code and see results here...

### 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.
`` ``