Problems/Stacks/Valid Parenthesis Expression
Stacks
easy

Valid Parenthesis Expression

Determine if a string containing different types of brackets is properly nested. This tests your understanding of data structures and algorithm design, specifically stacks, which are fundamental in many software engineering contexts.

stackdata structuresstringalgorithmvalidation

Problem Statement

Given a string composed of the characters '(', ')', '[', ']', '{', and '}', determine whether the input string represents a valid arrangement of brackets. A valid arrangement means that each opening bracket has a corresponding closing bracket of the same type, and the brackets are closed in the correct order. An empty string is also considered valid.

Example 1
Input: ({[]})
Output: True
The brackets are properly nested and closed in the correct order.
Example 2
Input: ([{])
Output: False
The closing square bracket ']' appears before the closing parenthesis ')', violating the correct order.
Constraints
  • -The string will only contain the characters '(', ')', '[', ']', '{', and '}'.
  • -The length of the string will be between 0 and 10000, inclusive.
  • -You should aim for a solution with linear time complexity.

Brute Force Approach

The brute force approach would involve checking every possible combination of bracket pairings. Imagine trying to match socks from a pile on the floor - you'd pick two at random, see if they match, and repeat. This is highly inefficient because you'd re-check many invalid combinations.

TimeO(n!)
SpaceO(1)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem