⚡Flashcard Drill➔
NeetCode #795LC-678MediumGreedyNC 150NC 250
← Back to All Problems

#795 · #678 · Valid Parenthesis String(有效的括号字符串)

📌 Problem Statement & Constraints

Given a string s containing only (, ) and *, where * may be treated as (, ), or the empty string, return true if s can be a valid parenthesis string. Constraints: 1 <= s.length <= 100.

💡 Core Algorithmic Approaches

  1. Track the range of possible open-parenthesis counts [lo, hi] instead of a single count.
  2. On ( both bounds increase; on ) both decrease (with lo clamped at 0); on * it can act as ) (decrease lo) or ( (increase hi).
  3. If hi ever drops below 0, there are too many closing parentheses and the string is invalid.
  4. At the end the string is valid iff lo == 0, meaning zero open parentheses is achievable.

💻 Benchmark Python3 Implementation

class Solution:
    def checkValidString(self, s: str) -> bool:
        lo = hi = 0                    # range of possible open counts
        for c in s:
            if c == "(":
                lo += 1
                hi += 1
            elif c == ")":
                lo = max(lo - 1, 0)
                hi -= 1
            else:                      # wildcard
                lo = max(lo - 1, 0)    # acts as ')'
                hi += 1                # acts as '('
            if hi < 0:
                return False           # too many ')'
        return lo == 0

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass over the string.
💾 Space Complexity
O(1): two counters.

⚠️ Interview Pitfalls & Follow-ups

  • Tracking a single greedy count: a fixed choice for * fails on strings such as (*)), so the full range is needed.
  • Clamping hi as well as lo: hi may legitimately drop below 0, which signals invalidity rather than being clamped.
  • Forgetting to clamp lo at 0: a negative lower bound is meaningless.
  • Returning hi == 0 at the end: the correct test is whether 0 lies in the range, i.e. lo == 0.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems