The problem
A string holds (, ) and *. Each * can stand for (, for ), or for nothing. Return true if some choice makes the brackets balanced: every ( closed by a later ), and no ) without an earlier (.
Examples
01
- Input
s = "()"
- Output
true
02
- Input
s = "(*)"
- Output
true
03
- Input
s = "(*))"
- Output
true
Constraints
- 1 ≤ s.length ≤ 100
- Each character is (, ) or *.
The idea
Without stars, one count of unclosed ( would do. With stars, the count could be several values at once — so track the range, from lo (every * read as )) to hi (every * read as (). Every value in between is possible too.
If hi ever drops below 0, even the most generous reading has an unmatched ): false. lo below 0 is just a reading that went wrong, so raise it back to 0. At the end, the string can be balanced exactly when 0 is in the range — when lo is 0.
- Time
- O(n)
- Space
- O(1)
Solution · every language run against every case
class Solution: def checkValidString(self, s: str) -> bool: # Track the range of possible counts of unclosed "(": each "*" may be "(", ")" or nothing. lo = hi = 0 for c in s: if c == "(": lo, hi = lo + 1, hi + 1 elif c == ")": lo, hi = lo - 1, hi - 1 else: lo, hi = lo - 1, hi + 1 if hi < 0: return False # even reading every "*" as "(" leaves too many ")" lo = max(lo, 0) # a count below zero is not a real reading; drop it return lo == 0 # some reading closes everything