Validate Matching Brackets

Question

The candidate is asked to write a function that validates whether a string of brackets is correctly matched and nested.

Codemia · Accepted Answer

To validate matching brackets, we can use a stack data structure. The idea is to push each opening bracket onto the stack and pop from the stack when we encounter a closing bracket. If the brackets are matched correctly, the stack should be empty at the end.

1. Initialize an empty stack.
2. Iterate through each character in the string:
   - If it is an opening bracket ('(', '{', '['), push it onto the stack.
   - If it is a closing bracket (')', '}', ']'), check if the stack is empty. If it is, return false. If not, pop the top of the stack and check if it matches the closing bracket.
3. After processing all characters, return true if the stack is empty, otherwise return false.

The time complexity of this algorithm is O(n), where n is the length of the input string, since we are processing each character once. The space complexity is O(n) in the worst case when all characters are opening brackets.

```python
def is_valid_brackets(s: str) -> bool:
    stack = []
    bracket_map = {')': '(', '}': '{', ']': '['}
    for char in s:
        if char in bracket_map.values():
            stack.append(char)
        elif char in bracket_map.keys():
            if not stack or stack[-1] != bracket_map[char]:
                return False
            stack.pop()
    return not stack
```
This function checks for valid brackets by using a stack to ensure that each opening bracket has a corresponding closing bracket.

Consider cases like an empty string, which should return true, or strings with only opening or only closing brackets, which should return false. Testing these edge cases ensures our solution is robust.

Validate Matching Brackets

ByteDance

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

ByteDance Site Reliability Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string