💬 Discord
Sign In
NeetCode #345LC-20EasyStackBlind 75NC 150NC 250
← Back to All Problems

#345 · #20 · Valid Parentheses(有效的括号)

📌 Problem Statement & Constraints

Given a string s containing only the characters (, ), {, }, [ and ], determine whether the brackets are correctly matched and nested. Constraints: 1 <= s.length <= 10^4.

💡 Core Algorithmic Approaches

  1. A stack is the natural structure: opening brackets are pushed, and a closing bracket must match the most recent unmatched opening bracket.
  2. Map each closing bracket to its opening partner so the check is a single dictionary lookup.
  3. If the stack is empty when a closing bracket arrives, or the top does not match, the string is invalid.
  4. At the end, the stack must be empty -- any leftover opening bracket is unmatched.

💻 Benchmark Python3 Implementation

class Solution:
    def isValid(self, s: str) -> bool:
        pairs = {")": "(", "]": "[", "}": "{"}
        st = []
        for ch in s:
            if ch in pairs:                # closing bracket
                if not st or st.pop() != pairs[ch]:
                    return False
            else:                          # opening bracket
                st.append(ch)
        return not st                      # no unmatched openings left

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each character is pushed or popped at most once.
💾 Space Complexity
O(n) for the stack in the worst case (a string of all opening brackets).

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting the final emptiness check: "(((" would be wrongly accepted.
  • Popping before checking for an empty stack: st.pop() on an empty list raises IndexError; the not st guard must come first.
  • Matching by bracket type rather than by pairing: "(]" would pass if you only compared the opening characters loosely.
  • Recursing on nested brackets: the stack handles arbitrary nesting with no recursion depth concerns.