MediumNeetCode150StringDynamic ProgrammingGreedy
Valid Parenthesis String
Check if string with '*' is valid.
Examples
Input
s = "(*)"
Output
true
* can be ( or ) or empty.
Constraints
- •
1 <= s.length <= 100 - •
s[i] is '(' or ')' or '*'
Approaches
Try all for '*'.
CodeT: O(3^n) | S: O(n) stack
dp[i][j] = valid with i open parens at pos j.
CodeT: O(n^2) | S: O(n^2)
Track low and high possible open count.
CodeT: O(n) | S: O(1)
def checkValidString(s):
lo=hi=0
for c in s:
if c=='(': lo+=1; hi+=1
elif c==')': lo-=1; hi-=1
else: lo-=1; hi+=1
lo=max(lo,0)
if hi<0: return False
return lo==0Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Recursion | O(3^n) | O(n) stack | Try all for '*'. |
| DP 2D | O(n^2) | O(n^2) | dp[i][j] = valid with i open parens at pos j. |
| Greedy Range | O(n) | O(1) | Track low and high possible open count. |
Recursion
T: O(3^n)S: O(n) stack
Try all for '*'.
DP 2D
T: O(n^2)S: O(n^2)
dp[i][j] = valid with i open parens at pos j.
Greedy Range
T: O(n)S: O(1)
Track low and high possible open count.
Common Mistakes
Not handling * at end
Wrong range update
Off-by-one