Valid Parentheses 15 XP Easy

LeetCode Ctrl+Enter Run Ctrl+S Save

This is LeetCode #20: Valid Parentheses — the #1 most asked stack problem! 🏗️

💡 Think of it like this: Imagine you're checking if all the doors in a building are properly closed. Every opening bracket ( [ { is like opening a door, and every closing bracket ) ] } is like closing one. They must match in the right order!

# Valid:   '(){}[]'  '({[]})'  '(())'  
# Invalid: '(]'      '([)]'    '(('

Why a Stack? The last door you opened must be the first one you close. That's exactly what a stack does — Last In, First Out (LIFO)!

The Algorithm:

1️⃣ Create an empty stack and a mapping of closing → opening brackets
2️⃣ For each character in the string:
• If it's an opening bracket → push it onto the stack
• If it's a closing bracket → check if the top of stack matches. If yes, pop. If no, INVALID!
3️⃣ At the end, if the stack is empty → VALID! If not → some brackets were never closed

💭 Challenge time! Now implement this yourself using the strategy above. The best way to learn is by doing! ⭐

Trace for '({[]})':

'(' → push → stack: ['(']
'{' → push → stack: ['(', '{']
'[' → push → stack: ['(', '{', '[']
']' → matches '[' → pop → stack: ['(', '{']
'}' → matches '{' → pop → stack: ['(']
')' → matches '(' → pop → stack: []
Stack empty → VALID ✓

Complexity: Time O(n) — one pass. Space O(n) — stack can hold n/2 opening brackets.

📋 Instructions

Implement `is_valid(s)` that returns True if the parentheses string is valid. Test with the provided examples.

Use a stack! Push opening brackets. For closing brackets, check if top of stack matches. If stack is empty at the end → all brackets matched!

⚠️ Try solving it yourself first — you'll learn more!

def isValid(s):
    stack = []
    match = {')': '(', ']': '[', '}': '{'}
    
    for char in s:
        if char in match:           # Closing bracket
            if stack and stack[-1] == match[char]:
                stack.pop()          # Match found!
            else:
                return False         # Mismatch!
        else:
            stack.append(char)       # Opening bracket → push
    
    return len(stack) == 0  # Empty stack = all matched!

🧪 Test Cases

Input

is_valid("()")

Expected

True

Boolean check

Input

is_valid("()[]{}")

Expected

True

Boolean check

Input

is_valid("{[]}")

Expected

False

Boolean check

← Previous Next Exercise →

main.py

Hi! I'm Rex 👋

Output

Ready. Press ▶ Run or Ctrl+Enter.

›