Valid Parentheses | Leetcode 20

Welcome to our deep dive on Valid Parentheses (Leetcode 20). This is the quintessential introductory problem for learning the Stack data structure!

Problem Statement

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: s = "()[]{}" => Output: true

Example 2: s = "(]" => Output: false

Approach: The Stack Data Structure O(N)

A Stack operates on a LIFO (Last-In, First-Out) principle. This is perfect for nested structures like parentheses. Whenever we see an opening bracket, we push it onto the stack. Whenever we see a closing bracket, the most recently seen (top of stack) opening bracket must perfectly match it!

1. Iterate through the string character by character.
2. If the character is an opening bracket ((, {, [), push it onto the stack.
3. If it is a closing bracket (), }, ]):
   • If the stack is empty, return false (no matching opening bracket).
   • Pop the top element from the stack.
   • If the popped bracket does not form a valid pair with the current closing bracket, return false.
4. After fully iterating, the stack must be entirely empty. If it has leftover opening brackets, return false.

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        matching_map = {')': '(', '}': '{', ']': '['}
        
        for char in s:
            if char in matching_map:
                # Get top element or a dummy mismatched char if stack is empty
                top_element = stack.pop() if stack else '#'
                
                if matching_map[char] != top_element:
                    return False
            else:
                stack.append(char)
                
        # Stack should be empty if all pairs matched
        return not stack

Complexity Analysis

Try it yourself!

Try this problem on LeetCode (20)