LeetCode Link: 20. Valid Parentheses

Problem Definition

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: false

Example 4:

Input: s = "([])"

Output: true

Constraints:

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

Thought Process

Validating parentheses with brackets is a classic use case for a stack. The stack’s LIFO (last-in, first-out) nature helps us match opening brackets with their corresponding closing brackets in the correct order.

Real-World Connections

  • When writing code, your editor checks for matching brackets. Under the hood, some logic resembling this stack-based approach often helps detect mismatches.
  • In operating systems (e.g., navigating directories with cd a/b/c/../../), there’s a stack-like mechanism ensuring you “pop” back to the correct directory.

Key Observations

There are three main ways brackets can be invalid:

  1. Left brackets leftover (i.e., you finish scanning the string, but the stack isn’t empty).
  2. Mismatched bracket types (e.g., [) or (]).
  3. Right bracket surplus (trying to pop from an empty stack or encountering a right bracket without a matching left).

To confirm the string is valid, you must ensure all opening brackets have corresponding closing brackets in the correct order. A solid approach is:

  1. Iterate through each character.
  2. If the character is an opening bracket, push the corresponding closing bracket onto the stack.
  3. If the character is a closing bracket, check if it matches the top of the stack.
    • If it doesn’t match or the stack is empty, return False.
    • Otherwise, pop from the stack.
  4. In the end, if the stack is empty, return True; otherwise, return False.

To better illustrate it, you can use the below interactive step-by-step example:

Python Implementation

Using stack:

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        
        for item in s:
            if item == '(':
                stack.append(')')
            elif item == '[':
                stack.append(']')
            elif item == '{':
                stack.append('}')
            elif not stack or stack[-1] != item:
                return False
            else:
                stack.pop()
        
        return True if not stack else False

Using dictionary:

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        mapping = {
            '(': ')',
            '[': ']',
            '{': '}'
        }
        for item in s:
            if item in mapping.keys():
                stack.append(mapping[item])
            elif not stack or stack[-1] != item: 
                return False
            else: 
                stack.pop()
        return True if not stack else False

Complexity Analysis

  • Time Complexity: O(n). You scan through the string once, and each character is processed in constant time (pushing/popping from a list).
  • Space Complexity: O(n). In the worst case (all opening brackets), you store n/2 items on the stack.

Conclusion & Key Takeaways

  1. Stack Fundamentals: Bracket matching is a classic stack problem. Understanding it helps in more complex scenarios (e.g., expression parsing).
  2. Error Handling: Always handle edge cases where brackets don’t match, the stack is empty when you try to pop, or leftover brackets remain.
  3. Clean & Reusable Code: Use a dictionary to map pairs and maintain a neat approach. This makes your code both concise and easy to read.