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
- Track the range of possible open-parenthesis counts
[lo, hi]instead of a single count. - On
(both bounds increase; on)both decrease (withloclamped at 0); on*it can act as)(decreaselo) or((increasehi). - If
hiever drops below 0, there are too many closing parentheses and the string is invalid. - 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
hias well aslo:himay legitimately drop below 0, which signals invalidity rather than being clamped. - Forgetting to clamp
loat 0: a negative lower bound is meaningless. - Returning
hi == 0at 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.