Domain 1EasyCORE

Valid Parentheses

The problem requires determining whether a given string containing only parentheses characters (`'('`, `')'`, `'{'`, `'}'`, `'['`, `']'`) is valid. A string is considered valid if: 1. Open brackets are closed by the same type of brackets. 2. Open brackets are closed in the correct order.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#String#Stack

20. Valid Parentheses

Model: qwen2.5-coder:14b
Topics: String,Stack
FAANG asked: 1
Acceptance rate: 40.0%


Problem Breakdown

The problem requires determining whether a given string containing only parentheses characters ('(', ')', '{', '}', '[', ']') is valid. A string is considered valid if:

  1. Open brackets are closed by the same type of brackets.
  2. Open brackets are closed in the correct order.

Inputs:

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

Outputs:

  • A boolean value indicating whether the input string is valid or not.

Implicit Constraints/Edge Cases:

  • The string can be empty, which should return true as there are no invalid parentheses.
  • The string length is between 1 and 10^4 characters.
  • The string consists only of the specified parentheses characters.

Intuition

A brute-force approach would involve checking each character in the string to see if it matches a closing parenthesis at some point later in the string. This would be inefficient, as it could potentially require nested loops with a time complexity of O(n^2).

The key insight is that we can use a stack data structure to efficiently match opening and closing parentheses. By pushing each opening parenthesis onto the stack and popping from the stack when a matching closing parenthesis is encountered, we can ensure that both conditions for a valid string are met.

Approach

  1. Initialize an empty stack.
  2. Iterate through each character in the string:
    • If the character is an opening parenthesis ('(', '{', or '['), push it onto the stack.
    • If the character is a closing parenthesis (')', '}', or ']'):
      • Check if the stack is empty. If it is, return false as there is no matching opening parenthesis.
      • Pop the top element from the stack and check if it matches the current closing parenthesis. If not, return false.
  3. After processing all characters, check if the stack is empty. If it is, return true; otherwise, return false.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the string. We iterate through each character in the string once.
  • Space Complexity: O(n) in the worst case, where all characters are opening parentheses and are pushed onto the stack.

Solution

def isValid(s: str) -> bool:
    # Dictionary to hold matching pairs of parentheses
    matching_parentheses = {')': '(', '}': '{', ']': '['}
    
    # Stack to keep track of opening parentheses
    stack = []
    
    for char in s:
        if char in matching_parentheses.values():
            # If it's an opening parenthesis, push onto the stack
            stack.append(char)
        elif char in matching_parentheses.keys():
            # If it's a closing parenthesis, check for matching opening parenthesis
            if not stack or stack.pop() != matching_parentheses[char]:
                return False
    
    # If stack is empty, all parentheses were matched correctly
    return not stack

Edge Cases Handled

  • Empty String: Returns true as there are no invalid parentheses.
  • Single Parenthesis: Returns false as a single parenthesis cannot be closed.
  • Nested Parentheses: Handles nested structures like "{[()]}" correctly.
  • Mismatched Parentheses: Detects mismatches like "([)]" and returns false.