Back to All Questions
Valid Parentheses
Amazon
String
Stack

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

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

Solution Walkthrough

This is a classic problem that can be elegantly solved using a stack data structure.

  1. Initialize an empty stack.
  2. Create a map to store the relationship between closing and opening brackets, e.g., { ')': '(', '}': '{', ']': '[' }.
  3. Iterate through each character of the input string s.
    • If the character is an opening bracket ((, {, [), push it onto the stack.
    • If the character is a closing bracket (), }, ]), check the stack. If the stack is empty or if the top element of the stack is not the corresponding opening bracket, the string is invalid. If it matches, pop the stack.
  4. After the loop, if the stack is empty, it means all brackets were correctly matched and closed, so the string is valid. If the stack is not empty, it means there are unclosed opening brackets, so the string is invalid.

The time complexity is O(n) because we process each character once. The space complexity is O(n) in the worst case (a string of all opening brackets).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22