Validate Nested Parentheses, Brackets, and Braces
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Online Assessment
Given a string `s` containing only `(`, `)`, `[`, `]`, `{`, and `}`, determine whether all brackets are correctly matched and nested. Return a Boolean.
A closing bracket must match the most recent opening bracket that has not yet been closed. Every opening bracket must eventually be closed.
### Constraints & Assumptions
- This practice version uses the standard six-character bracket alphabet.
- `s` may be empty; an empty string is valid.
- The input contains at most 100,000 characters. This is a practice bound for choosing a linear algorithm.
- Adjacent complete groups are allowed: `()[]{}` is valid.
- Matching bracket counts alone are insufficient: `([)]` is invalid.
### Examples
- Input: `"{[()]}[]"`. Output: `true`. Both the nested group and the final pair close in the correct order.
- Input: `"([)]"`. Output: `false`. The `)` appears while `[` is still the most recent unmatched opener.
### Clarifying Questions to Ask
- Does the alphabet contain only brackets, or must other characters be ignored or rejected?
- Is the empty string valid?
- Is the input available at once, or must the same check work incrementally over chunks?
```hint Remember the unfinished nesting
After reading a prefix, which unmatched opening bracket determines the only legal next closing bracket?
```
Overview: Validate nested parentheses, brackets, and braces with correct handling of empty input, mismatched closing symbols, and unfinished groups.
Given a string `s` containing only `(`, `)`, `[`, `]`, `{`, and `}`, determine whether all brackets are correctly matched and nested. Return a Boolean.
A closing bracket must match the most recent opening bracket that has not yet been closed. Every opening bracket must eventually be closed.
### Constraints & Assumptions
- This practice version uses the standard six-character bracket alphabet.
- `s` may be empty; an empty string is valid.
- The input contains at most 100,000 characters. This is a practice bound for choosing a linear algorithm.
- Adjacent complete groups are allowed: `()[]{}` is valid.
- Matching bracket counts alone are insufficient: `([)]` is invalid.
### Examples
- Input: `"{[()]}[]"`. Output: `true`. Both the nested group and the final pair close in the correct order.
- Input: `"([)]"`. Output: `false`. The `)` appears while `[` is still the most recent unmatched opener.
### Clarifying Questions to Ask
- Does the alphabet contain only brackets, or must other characters be ignored or rejected?
- Is the empty string valid?
- Is the input available at once, or must the same check work incrementally over chunks?
```hint Remember the unfinished nesting
After reading a prefix, which unmatched opening bracket determines the only legal next closing bracket?
```
Constraints
- The input contains only (, ), [, ], {, and } and has length 0 through 100000.
- A closer must match the most recent unmatched opener; every opener must eventually close.
- Empty input is valid and adjacent complete groups are allowed.
- Return a boolean; equal bracket counts alone do not establish correct nesting.
Examples
Input: ('{[()]}[]',)
Expected Output: True
Explanation: Nested and adjacent groups can both be valid.
Input: ('([)]',)
Expected Output: False
Explanation: Matching counts do not permit crossing nesting.