Validate bracket sequence
Company: Intuit
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
Given a string `s` containing only the characters `(`, `)`, `[`, `]`, `{`, and `}`, determine whether the brackets are properly matched.
A string is valid if:
- Every opening bracket is closed by a bracket of the same type.
- Brackets are closed in the correct order.
- No closing bracket appears without a matching earlier opening bracket.
Return `true` if the string is valid and `false` otherwise.
Example 1:
- Input: `s = "()[]{}"`
- Output: `true`
Example 2:
- Input: `s = "([)]"`
- Output: `false`
Example 3:
- Input: `s = "{[]}"`
- Output: `true`
Be prepared to write and run a few test cases, including edge cases such as the empty string.
Quick Answer: This question evaluates understanding of bracket matching and string parsing, testing competency with basic data structures and algorithmic reasoning such as stack-based matching and correct handling of nested delimiters.
Given a string `s` containing only the characters `(`, `)`, `[`, `]`, `{`, and `}`, determine whether the bracket sequence is valid.
A string is valid if:
- Every opening bracket is closed by a bracket of the same type.
- Brackets are closed in the correct order.
- No closing bracket appears without a matching earlier opening bracket.
Return `True` if the string is valid and `False` otherwise.
Constraints
- 0 <= len(s) <= 100000
- s contains only the characters '(', ')', '[', ']', '{', and '}'
Examples
Input: "()[]{}"
Expected Output: True
Explanation: Each bracket is properly opened and closed in the correct order.
Input: "([)]"
Expected Output: False
Explanation: The ')' tries to close '(' while '[' is still open, so the order is invalid.
Hints
- Use a stack to keep track of opening brackets as you scan the string from left to right.
- When you see a closing bracket, it must match the most recent unmatched opening bracket.