Amazing solution! One small way to improve it ever so slightly is, instead of using an array to store all the sub-problems and then doing `any` or `all` on it, we can simply save a Boolean variable. We can initialize it as "result = NULL" and do something like: "if (result == null) { helper(s) } else if (c=='&') { helper(s) && result!! } else { helper(s) || result!! }" This way we can improve on a large array of booleans, in case of many, many subproblems for a specific & or |
I always get intrigued by these kinds of solution. I heard somewhere that coming up with these solutions in an interview is not easy, if you have never seen in before. I was think in the stack route. I have a Google interview next month (fingers-crossed), will be referring your Neetcode 150 for the preparation for sure.
I just thought about prefix notation and how we use a stack there as soon as I saw this problem. And to be honest, the stack approach seems more intuitive, easy, and equally optimal as well.
I found this to be the easiest to understand in my opinion..... Definitely an annoying problem, would not have any clue how to solve this in a real interview class Solution: def parseBoolExpr(self, expression: str) -> bool: stack = [] for c in expression: if c == ')': # If we've reached the end of a sub expression sub_expression = [] while stack[-1] != '(': sub_expression.append(stack.pop()) stack.pop() # Remove the '(' operator = stack.pop() if operator == '!': # Evaluate the sub_expressions result = not sub_expression[0] elif operator == '&': result = all(sub_expression) elif operator == '|': result = any(sub_expression) stack.append(result) elif c != ',': # Anything that's not a comma, add it to the stack if c == 't': stack.append(True) elif c == 'f': stack.append(False) else: stack.append(c) return stack[0]
Now I see how deceiving the recursive approach is. The problem looks naturally recursive, but the implementation is complicated. I used stack mostly automatically and it turned out way simpler. P.S. Something has broken at Leetcode. I have never got solution time less than ~30ms in the past year, but recently I am getting 10ms and even 0ms evaluation. They may have upgraded Python to a new version.
index is being shared for all the recursive calls so no need for any parameters you can kind of think it as a while loop where we are jumping the index
Could skip further evaluation with first encounter for _false_ in &() and _true_ in |()? Example: &(t,&(t,&(f,&(t,&(t,&(t,&(t,&(t,&(t))))))))) with reaching the f there is no need to evaluate rest of the &() case.
O(n) stack solution: class Solution: def parseBoolExpr(self, expression: str) -> bool: reduce = { '&': lambda x, y: x and y, '|': lambda x, y: x or y } stack = [] opened = False for c in expression: if c in {'&', '|', '!', '('}: stack.append(c) elif c == 't': stack.append(True) elif c == 'f': stack.append(False) elif c == ')': arr = [] while stack[-1] != '(': arr.append(stack.pop()) stack.pop() if stack[-1] in reduce: op = stack.pop() stack.append(functools.reduce(reduce[op], arr)) elif stack[-1] == '!': stack.pop() stack.append(not arr[0]) return stack[0]
Below is my 2 stack solution. In case anyone need it. class Solution: def parseBoolExpr(self, expression: str) -> bool: opStack = [] resStack = [] for ch in expression: if ch in ('!', '&', '|'): opStack.append(ch) else: if ch == ')': boolVals = [] while resStack[-1] != '(': boolVals.append(resStack.pop()) # remove extra '(' from the top resStack.pop() op = opStack.pop() if op == '!': val = boolVals.pop() if val == 'f': resStack.append('t') else: resStack.append('f') elif op == '|': res = 'f' for val in boolVals: if val == 't': res = 't' break resStack.append(res) elif op == '&': res = 't' for val in boolVals: if val == 'f': res = 'f' break resStack.append(res) else: resStack.append(ch) # print(opStack, resStack) return True if resStack[0] == 't' else False
Problem is very easy and straight forward using Stack; you are complicating it using recursion.
Also an optimal solution with O(n) time and space complexity.
Could you share your code
Can you share the Stack solution?
We are using a stack.He is using a call stack that's it😂.
of course bro this problem is basic stack problem i dont why neetcode do this kind of solution he want to chenge himself for beginners also
Amazing solution! One small way to improve it ever so slightly is, instead of using an array to store all the sub-problems and then doing `any` or `all` on it, we can simply save a Boolean variable. We can initialize it as "result = NULL" and do something like:
"if (result == null) { helper(s) } else if (c=='&') { helper(s) && result!! } else { helper(s) || result!! }"
This way we can improve on a large array of booleans, in case of many, many subproblems for a specific & or |
Very elegant solution
I always get intrigued by these kinds of solution. I heard somewhere that coming up with these solutions in an interview is not easy, if you have never seen in before. I was think in the stack route. I have a Google interview next month (fingers-crossed), will be referring your Neetcode 150 for the preparation for sure.
good luck!
Bro gave a legendary solution! In every run it beats 100% of the solutions
this is pure genius.. how long will it take for a noob like me to come as powerful as you in the IDE?
this is my first time seeing neetcode write unclear code.
Wouldn't have understood this problem without you
any reason to do it this way compared to much simpler 2 stack solution?
even 1 stack is sufficient
This gets more interesting if you now add precedence.
I just thought about prefix notation and how we use a stack there as soon as I saw this problem.
And to be honest, the stack approach seems more intuitive, easy, and equally optimal as well.
It's the fist time I think my own solution is more elegant that the solution of the teacher :)
amazing code explanation. great work
I solved it by using 2 stacks: first for operations, second for "t","f"
The iterative solution 'going inside-outside" is way more elegant
namastey!
I found this to be the easiest to understand in my opinion..... Definitely an annoying problem, would not have any clue how to solve this in a real interview
class Solution:
def parseBoolExpr(self, expression: str) -> bool:
stack = []
for c in expression:
if c == ')': # If we've reached the end of a sub expression
sub_expression = []
while stack[-1] != '(':
sub_expression.append(stack.pop())
stack.pop() # Remove the '('
operator = stack.pop()
if operator == '!': # Evaluate the sub_expressions
result = not sub_expression[0]
elif operator == '&':
result = all(sub_expression)
elif operator == '|':
result = any(sub_expression)
stack.append(result)
elif c != ',': # Anything that's not a comma, add it to the stack
if c == 't':
stack.append(True)
elif c == 'f':
stack.append(False)
else:
stack.append(c)
return stack[0]
Now I see how deceiving the recursive approach is. The problem looks naturally recursive, but the implementation is complicated. I used stack mostly automatically and it turned out way simpler.
P.S. Something has broken at Leetcode. I have never got solution time less than ~30ms in the past year, but recently I am getting 10ms and even 0ms evaluation. They may have upgraded Python to a new version.
I am still confused about helper() being used with no parameters, can anyone provide more details?
index is being shared for all the recursive calls so no need for any parameters you can kind of think it as a while loop where we are jumping the index
Could skip further evaluation with first encounter for _false_ in &() and _true_ in |()?
Example: &(t,&(t,&(f,&(t,&(t,&(t,&(t,&(t,&(t)))))))))
with reaching the f there is no need to evaluate rest of the &() case.
indeed, slight optimization
why didn't you use stack for this
My non-refactored code got better performance than yours - do I get a referral? ;)
Btw: huge shame on you for not using switch/match case loops :(
that's not a hard question if you know top-down parser
Just use the freaking stack, man
im switching to healthcare to be a doctor without borders because i like crossing boundaries. please stop uploading.
O(n) stack solution:
class Solution:
def parseBoolExpr(self, expression: str) -> bool:
reduce = {
'&': lambda x, y: x and y,
'|': lambda x, y: x or y
}
stack = []
opened = False
for c in expression:
if c in {'&', '|', '!', '('}:
stack.append(c)
elif c == 't':
stack.append(True)
elif c == 'f':
stack.append(False)
elif c == ')':
arr = []
while stack[-1] != '(':
arr.append(stack.pop())
stack.pop()
if stack[-1] in reduce:
op = stack.pop()
stack.append(functools.reduce(reduce[op], arr))
elif stack[-1] == '!':
stack.pop()
stack.append(not arr[0])
return stack[0]
How is the performance?
@@floriankubiak7313 super quick, "beats 97.36% of python3 submissions"
python is love
nah bro too many abstraction ( i love python )
First!
Below is my 2 stack solution. In case anyone need it.
class Solution:
def parseBoolExpr(self, expression: str) -> bool:
opStack = []
resStack = []
for ch in expression:
if ch in ('!', '&', '|'):
opStack.append(ch)
else:
if ch == ')':
boolVals = []
while resStack[-1] != '(':
boolVals.append(resStack.pop())
# remove extra '(' from the top
resStack.pop()
op = opStack.pop()
if op == '!':
val = boolVals.pop()
if val == 'f':
resStack.append('t')
else:
resStack.append('f')
elif op == '|':
res = 'f'
for val in boolVals:
if val == 't':
res = 't'
break
resStack.append(res)
elif op == '&':
res = 't'
for val in boolVals:
if val == 'f':
res = 'f'
break
resStack.append(res)
else:
resStack.append(ch)
# print(opStack, resStack)
return True if resStack[0] == 't' else False