TIC
The Interns Company

Valid Parentheses

EasyAcceptance: 40.6%
StringStack

Problem Statement

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if: Open brackets must be closed by the same type of brackets, and Open brackets must be closed in the correct order.

Constraints:

  • 1 <= s.length <= 10^4
  • s consists of parentheses only '()[]{}'.

Input Format:

  • A string s containing just the characters '(', ')', '{', '}', '[' and ']'

Output Format:

  • Return true if the input string is valid, otherwise return false.

Examples:

Example 1:

Input:

s = "()"

Output:

true

Explanation:

The parentheses in the string form a valid pair.

Example 2:

Input:

s = "()[]{}"

Output:

true

Explanation:

All the brackets in the string form valid pairs and are closed in the correct order.

Example 3:

Input:

s = "(]"

Output:

false

Explanation:

The bracket types don't match ('(' and ']').

Example 4:

Input:

s = "([)]"

Output:

false

Explanation:

The brackets aren't closed in the correct order.

Example 5:

Input:

s = "{[]}"

Output:

true

Explanation:

All the brackets form valid pairs and are closed in the correct order.

Solutions

Stack Approach

Time: O(n)
Space: O(n)

Use a stack to keep track of opening brackets. When a closing bracket is encountered, check if it matches the top of the stack.

Algorithm Walkthrough

Example input:

Step-by-step execution:

  1. s = "({[]})"
  2. Initialize empty stack
  3. Char '(': Push to stack -> stack = ['(']
  4. Char '{': Push to stack -> stack = ['(', '{']
  5. Char '[': Push to stack -> stack = ['(', '{', '[']
  6. Char ']': Matches top of stack '[', pop -> stack = ['(', '{']
  7. Char '}': Matches top of stack '{', pop -> stack = ['(']
  8. Char ')': Matches top of stack '(', pop -> stack = []
  9. Stack is empty at the end, return true

Hints

Hint 1
Consider using a data structure to keep track of open brackets.
Hint 2
When you encounter a closing bracket, it should match the most recently seen open bracket.
Hint 3
A stack can be a useful data structure for this problem.

Video Tutorial

Valid Parentheses - Stack Approach

YouTube•Learn the Valid Parentheses solution step-by-step

Video tutorials can be a great way to understand algorithms visually

Visualization

Visualize the stack operations as each character is processed.

Key visualization elements:

  • current character
  • stack state
  • matching brackets

Asked By

AmazonGoogleMicrosoftFacebookTwitterUberAirbnb

Implementation Notes

This is a classic stack problem that demonstrates how stacks can efficiently solve bracket matching problems.