# Valid Brackets

## Course launching November 17, 2020

**Follow me on YouTube** for free coding interview videos.

Users who sign up for the email list will receive an exclusive 75% discount at launch.

**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 bracks 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 close) and don't overlap.

```
() // true
][ // false
{}[]() // true
{[]} // true
([) // false
{(}) // false
{[(([{}]))]} // true
{[]{()}} // true
```

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