Katkat
Back

Validate Bracket Sequence

WeRideSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

This problem tests the ability to manage nested structures using a stack to ensure that all opening brackets are closed in the correct order and type.

Problem: Valid Bracket Sequence

Given a string s containing only the characters '(', ')', '{', '}', '[', and ']', write a function isValid(s) that determines if the input string is valid.

An input string is valid if:

  1. Open brackets are closed by the same type of brackets.
  2. Open brackets are closed in the correct order.
  3. Every close bracket has a corresponding open bracket of the same type.

Function Signature

def isValid(s: str) -> bool:

Constraints

  • 1 <= len(s) <= 10^4
  • s consists of parentheses and brackets only: ()[]{}

Examples

Example 1: Input: s = "()[]{}" Output: True

Example 2: Input: s = "([)]" Output: False Explanation: The square bracket is closed before the round bracket, which violates the LIFO (Last-In-First-Out) order.

Example 3: Input: s = "{[]}" Output: True

Edge Cases

  • Empty strings or strings with an odd length should return False immediately.
  • Strings with only closing brackets at the start should return False.

Hints

Hint 1

A stack data structure is ideal for tracking open brackets as they appear.

Hint 2

When you encounter a closing bracket, check if it matches the bracket at the top of the stack.

Hint 3

If you reach the end of the string and the stack is not empty, there are unclosed brackets remaining.

Follow-up questions

  • How would you modify your solution to handle alphanumeric characters (e.g., 'a(b)c') that should be ignored?
  • What is the time and space complexity of your solution, and can you optimize the space if the string only contained one type of bracket?
  • How would you extend this logic to support a custom set of bracket pairs defined by a dictionary or hash map?