loading

20. Valid Parentheses — Step-by-Step Visualization

easyLeetCode #20StackString

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. **Example 1:** Input: `s = "()"` Output: `true` **Example 2:** Input: `s = "()[]{}"` Output: `true` **Example 3:** Input: `s = "([])"` Output: `true`

Algorithm Pattern

Stack

Key Idea

Use a stack to keep track of the most recent opening bracket. When you see a closing bracket, it must match the top of the stack.

Step-by-Step Approach

  1. Initialize an empty stack.
  2. Traverse the string `s` character by character.
  3. If the current character is an opening bracket, push it onto the stack.
  4. If it's a closing bracket, check if the stack is empty (if so, it's invalid) or if the top of the stack matches the closing bracket type.
  5. If it's a match, pop the stack.
  6. If it's a mismatch, the string is invalid.
  7. At the end of traversal, if the stack is completely empty, the string is valid.

Common Gotchas

  • Don't forget to check if the stack is empty BEFORE trying to pop it when evaluating a closing bracket.
  • An empty stack at the end signifies validity. Leftover opening brackets indicate invalidity.

Related Problems

← All problems