Katkat
Back

Check whether brackets are balanced

Walmart LabsSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to handle nested structures using a stack data structure to track opening symbols and verify matching closing symbols.

Problem Statement

Given a string s containing only the characters '(', ')', '{', '}', '[' and ']', determine 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.

Implement the function: def is_valid(s: str) -> bool:

Constraints

  • 1 <= len(s) <= 10^4
  • The string consists only of parentheses, square brackets, and curly braces.

Examples

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

Example 2: Input: s = "([)]" Output: False Explanation: The brackets are closed in the wrong order; the square bracket must be closed before the parenthesis.

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

Edge Cases

  • Empty strings (or strings with odd lengths).
  • Strings starting with a closing bracket (e.g., "]").
  • Strings with unclosed brackets (e.g., "(()").

Hints

Hint 1

Consider using a stack to keep track of the opening brackets as you encounter them.

Hint 2

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

Hint 3

If the stack is empty when you see a closing bracket, or if the stack is not empty after processing the entire string, the string is invalid.

Follow-up questions

  • How would you modify your solution to handle additional characters like letters or numbers that should be ignored?
  • What is the space complexity of your solution, and can you describe a scenario where the space complexity is O(n)?
  • How would you adapt this logic to support multi-character brackets, such as 'begin' and 'end' tags?