← all entries
A-021● Day 212026.05.23easyleetcode #20neetcode150

Valid Parentheses

#string#stack
↗ leetcode #20 · valid-parentheses
01

Problem

· problem
P.021

Valid Parentheses

↗ leetcode #20

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.

constraints
  • · 1 ≤ s.length ≤ 10^4
  • · s consists of parentheses only '()[]{}'
// paraphrased summary — see source for full text
examples
example 1input → output
"()"
true
example 2input → output
"()[]{}"
true
example 3input → output
"(]"
false
example 4input → output
"([])"
true
example 5input → output
"([)]"
false
02

Pre-solve

· pre-solve
● 1list shown→● 2select→● 3reveal
  • ☐
    Must opening and closing brackets match in type?
  • ☐
    Is the order of nested brackets important?
  • ☐
    Is counting opening and closing brackets sufficient?
  • ☐
    Is a stack data structure essential?
  • ☐
    Should the string be processed backwards?
  • ☐
    What does an empty stack at the end signify?
check the items you would ask, then press confirm
// session-only state — refresh resets (repeatable practice)
03

Logic Structure

· logic
● 1slots shown→● 2pick per slot→● 3reveal
// pick one code line per slot to assemble the algorithm flow. no typing — just the logic skeleton.
step 1· Initialize closing-to-opening map
○
bracketMap = {")": "(", "]": "[", "}": "{"}
○
bracketMap = {"(": ")", "[": "]", "{": "}"}
○
bracketMap = {"()", "[]", "{}"}
step 2· Initialize empty stack
○
stack = []
○
stack = {}
○
stack = set()
step 3· Iterate through each character
○
for c in s:
○
for c in s.reverse():
○
for i in range(len(s) - 1):
step 4· Handle opening brackets│ │ nested
○
stack.append(c)
○
stack.pop()
○
return True
step 5· Validate closing bracket│ │ nested
○
if not stack or stack[-1] != bracketMap[c]:
○
if stack or stack[-1] != bracketMap[c]:
○
if stack[-1] == bracketMap[c]:
step 6· Pop matched opening bracket│ │ nested
○
stack.pop()
○
stack.append(c)
○
return True
step 7· Return validity result
○
return not stack
○
return stack
○
return bool(stack)
pick one option per slot
// format: slot — recursive / DP patterns use ordering / state-first formats. ADR-08 follow-up.
04

Solve · Trace

· solve
solution.py
1
class Solution:
2
    def isValid(self, s: str) -> bool:
3
        bracketMap = {")": "(", "]": "[", "}": "{"}
4
        stack = []
5
6
        for c in s:
7
            if c not in bracketMap:
8
                stack.append(c)
9
                continue
10
            if not stack or stack[-1] != bracketMap[c]:
11
                return False
12
            stack.pop()
13
14
        return not stack
mental dry-run cases
// walk each case in your head; expand the worked example below if stuck.
case 1
"()"
→
true
case 2
"()[]{}"
→
true
case 3
"(]"
→
false
case 4
"([])"
→
true
case 5
"([)]"
→
false
// UI does not walk-through — you do the dry-run mentally. Expand the worked example if stuck.