Oh, the operations dictionary with the lambda’s was quite genius! Never came to mind I could use lambdas like that! Also, in the tags it says the question is about Dynamic Programming. How exactly are we doing Dynamic Programming here?
I don't believe DP would offer any performance improvements, for the same reason that it doesn't in problems like Combination Sum, Subsets & Permutations. Maybe someone else can provide a longer explanation.
here is a solution with caching, memoization ( i hate bottom up-ization) class Solution { Map operators = new HashMap(); Map dp = new HashMap();
public List diffWaysToCompute(String expression) { operators.put('+',(a,b)->a+b); operators.put('-',(a,b)->a-b); operators.put('*',(a,b)->a*b); int l=0;int r = expression.length()-1; return computeDfs(l,r,expression.toCharArray()); }
public List computeDfs(int l, int r, char[] ca){
int i=l; List res= new ArrayList(); if(l==r){ res.add(Integer.parseInt(""+ca[l])); return res; } if(l+1==r){ res.add(Integer.parseInt(""+ca[l]+ca[r])); return res; } String key = l+","+r; if(dp.containsKey(key)){ return dp.get(key); } while(i
There is a bit of repeated work, but not enough to make a difference. For instance, when we compute any expression (a+b), we can think about how many times it will be called. If we do a partition such as (a+b).... it's called once. Maybe we the partition the expression (a+b+c)..., and then (a+b) is called once more. And maybe we then partition to (a+b+c+d)...., where it will be called once more. So on avg each of these expressions is called around N times, expressions with double this length are called around N/2 times, and so on. The entire input expression will be called once. Our time complexity is still exponential (~2^N) so dividing this by the average of all the repeated work operations will be at most N, and so 2^N / N (the denominator is actually smaller than N) is still O(2^N). this is just how I kind of thought of it in my head, but would welcome any further notes/corrections to this as it is not rigorous
Problems like these just make me lose all my motivation. I don't think I'm ever gonna make it in big tech coz no matter how many of these I solve, even the medium ones seem extremely difficult.
Hey @neetcodeio, i think you might find these VS Code shortcuts (that also work on Leetcode's editor) useful. Ctrl + D -> select next occurence Shift + Alt + downarrow -> duplicate current line (do this repeatedly to get several duplicates) Shift + Del -> delete current line I've watched several of your videos where I see you doing some manual stuff and I think these might help.
Tbf the editorials on lc are often not that good.. I'm working on adding editorials to all the problems on neetcode.io in several languages with time & space complexity
I tried to generate all possible combinations of valid expressions by inserting brackets. However, backtracking generates more combinations that return the same sum in multiple ways.
All thanks to your nice explanations, I watched this video for less than 5 minutes and wrote the correct code in one go. I am a recent grad and got a great job, all thanks to you. Can't thank you enough.
the first time i did the question it worked fine but the second time i attempted it it gave me this error ValueError: invalid literal for int() with base 10: '0+1' the code was same in the both cases why is this happening?
Your result should be a list of integers and in base case slicing of expression is done which is already in string format that's why conversion is required.
I have a question, but please be honest. Were you able ot solve this on your own, or did you have to look at the editorial? Trust me you will not lose a subscriber if you say you had to look at the editorial.
Another alternative to using lambdas is relying on the operator Python module: import operator operators = {"+": operator.add, "-": operator.sub, "*": operator.mul}
solution in java with chaching class Solution { Map operators = new HashMap(); Map dp = new HashMap();
public List diffWaysToCompute(String expression) { operators.put('+',(a,b)->a+b); operators.put('-',(a,b)->a-b); operators.put('*',(a,b)->a*b); int l=0;int r = expression.length()-1; return computeDfs(l,r,expression.toCharArray()); }
public List computeDfs(int l, int r, char[] ca){
int i=l; List res= new ArrayList(); if(l==r){ res.add(Integer.parseInt(""+ca[l])); return res; } if(l+1==r){ res.add(Integer.parseInt(""+ca[l]+ca[r])); return res; } String key = l+","+r; if(dp.containsKey(key)){ return dp.get(key); } while(i
@@artem_r most programmers do not, anything that is algorithmic and of importance has been solved by someone smarter than you or me or him and you’re using that library
@@takeuchi5760 that is true. But yes I’m literally saying, “did you have to do anything as challenging as a leetcode medium or hard actually in the job” I love leetcode, but it’s just gatekeeping at the end of the day, and if you enjoy it you’re fortunate
As lamda is anonymous function in python. Similarly, in C++, anonymous function exists but mapping like JavaScript object, python is not possible in C++ but I think for that you have to create a map which maps operator to its corresponding function pointers created via anonymous function in C++. Instead, you can use below code to get somewhat working like lamda function: auto operations = [](int a, int b, char op) -> int { switch(op) { case '+' : return a + b; case '-' : return a - b; case '*' : return a * b; default : return INT_MIN; } }; cout
unordered_map mp = { { "+" , [] (int a, int b) { return a + b; } }, { "-" , [] (int a, int b) { return a - b; } }, { "*" , [] (int a, int b) { return a * b; } }, { "/" , [] (int a, int b) { return a / b; } } }; call using mp[op](a, b);
Oh, the operations dictionary with the lambda’s was quite genius! Never came to mind I could use lambdas like that!
Also, in the tags it says the question is about Dynamic Programming. How exactly are we doing Dynamic Programming here?
I don't believe DP would offer any performance improvements, for the same reason that it doesn't in problems like Combination Sum, Subsets & Permutations.
Maybe someone else can provide a longer explanation.
here is a solution with caching, memoization ( i hate bottom up-ization)
class Solution {
Map operators = new HashMap();
Map dp = new HashMap();
public List diffWaysToCompute(String expression) {
operators.put('+',(a,b)->a+b);
operators.put('-',(a,b)->a-b);
operators.put('*',(a,b)->a*b);
int l=0;int r = expression.length()-1;
return computeDfs(l,r,expression.toCharArray());
}
public List computeDfs(int l, int r, char[] ca){
int i=l;
List res= new ArrayList();
if(l==r){
res.add(Integer.parseInt(""+ca[l]));
return res;
}
if(l+1==r){
res.add(Integer.parseInt(""+ca[l]+ca[r]));
return res;
}
String key = l+","+r;
if(dp.containsKey(key)){
return dp.get(key);
}
while(i
There is a bit of repeated work, but not enough to make a difference. For instance, when we compute any expression (a+b), we can think about how many times it will be called. If we do a partition such as (a+b).... it's called once. Maybe we the partition the expression (a+b+c)..., and then (a+b) is called once more. And maybe we then partition to (a+b+c+d)...., where it will be called once more. So on avg each of these expressions is called around N times, expressions with double this length are called around N/2 times, and so on. The entire input expression will be called once. Our time complexity is still exponential (~2^N) so dividing this by the average of all the repeated work operations will be at most N, and so 2^N / N (the denominator is actually smaller than N) is still O(2^N).
this is just how I kind of thought of it in my head, but would welcome any further notes/corrections to this as it is not rigorous
leetcode tags calls everything dp, but i personally think this is more divide and conquer than dp
Problems like these just make me lose all my motivation. I don't think I'm ever gonna make it in big tech coz no matter how many of these I solve, even the medium ones seem extremely difficult.
Hey @neetcodeio, i think you might find these VS Code shortcuts (that also work on Leetcode's editor) useful.
Ctrl + D -> select next occurence
Shift + Alt + downarrow -> duplicate current line (do this repeatedly to get several duplicates)
Shift + Del -> delete current line
I've watched several of your videos where I see you doing some manual stuff and I think these might help.
wow. your solution way more better than in editorial.
Tbf the editorials on lc are often not that good.. I'm working on adding editorials to all the problems on neetcode.io in several languages with time & space complexity
how do you come up with this type of logic ?? i couldn't able to think a solution like that and after seeing this solution it became damn easy to me.
Hey Neetcode, how could you come up with these approaches?
pretty good thing mann
I tried to generate all possible combinations of valid expressions by inserting brackets. However, backtracking generates more combinations that return the same sum in multiple ways.
Thanks man, I could do it on paper but couldn't come up with the left and right parameter thing. Thanks it was very good solution.
base case trick was excellent. i remember using eval on all the n1,n2 was very inelegant in comparison.
Very beautifully coded ! Thank you for the daily problems
I can do this in java too with
Map
Even if you dont know BinaryOperator exists just create your own functional interface
@FunctionalInterface
interface Operator {
int operate(int x, int y);
}
With this we can do
map.get('-').operate(1,2)
All thanks to your nice explanations, I watched this video for less than 5 minutes and wrote the correct code in one go. I am a recent grad and got a great job, all thanks to you. Can't thank you enough.
the first time i did the question it worked fine but the second time i attempted it it gave me this error
ValueError: invalid literal for int() with base 10: '0+1'
the code was same in the both cases
why is this happening?
i dont understand the integer conversion base case he added at the end can someone explain
Your result should be a list of integers and in base case slicing of expression is done which is already in string format that's why conversion is required.
I have a question, but please be honest. Were you able ot solve this on your own, or did you have to look at the editorial? Trust me you will not lose a subscriber if you say you had to look at the editorial.
Another alternative to using lambdas is relying on the operator Python module:
import operator
operators = {"+": operator.add, "-": operator.sub, "*": operator.mul}
ngl that lambda dict was clean af, i always forget they exist
I think there is some repeated work we can then also do some caching based on l+','+r
solution in java with chaching
class Solution {
Map operators = new HashMap();
Map dp = new HashMap();
public List diffWaysToCompute(String expression) {
operators.put('+',(a,b)->a+b);
operators.put('-',(a,b)->a-b);
operators.put('*',(a,b)->a*b);
int l=0;int r = expression.length()-1;
return computeDfs(l,r,expression.toCharArray());
}
public List computeDfs(int l, int r, char[] ca){
int i=l;
List res= new ArrayList();
if(l==r){
res.add(Integer.parseInt(""+ca[l]));
return res;
}
if(l+1==r){
res.add(Integer.parseInt(""+ca[l]+ca[r]));
return res;
}
String key = l+","+r;
if(dp.containsKey(key)){
return dp.get(key);
}
while(i
So elegant!
would you please explain how do we know that we have only 3 operators?
It was mentioned in the constraints:
"expression consists of digits and the operator '+', '-', and '*'"
Memoization could help a little, no?
thanks again buddy
this code was sweet like a laddoo
Did being good at leetcode actually help you when working at Google?
if you work in algorithms heavy problems, why not? Eg. compression webp
Problem solving skills are never wasted.
@@artem_r most programmers do not, anything that is algorithmic and of importance has been solved by someone smarter than you or me or him and you’re using that library
@@takeuchi5760 that is true. But yes I’m literally saying, “did you have to do anything as challenging as a leetcode medium or hard actually in the job” I love leetcode, but it’s just gatekeeping at the end of the day, and if you enjoy it you’re fortunate
@@rdubb77 import oriented programming is the best paradigm
Can anyone tell me how to implement "operations dictionary with the lambda" in c++ ?
As lamda is anonymous function in python. Similarly, in C++, anonymous function exists but mapping like JavaScript object, python is not possible in C++ but I think for that you have to create a map which maps operator to its corresponding function pointers created via anonymous function in C++. Instead, you can use below code to get somewhat working like lamda function:
auto operations = [](int a, int b, char op) -> int {
switch(op) {
case '+' : return a + b;
case '-' : return a - b;
case '*' : return a * b;
default : return INT_MIN;
}
};
cout
unordered_map mp = {
{ "+" , [] (int a, int b) { return a + b; } },
{ "-" , [] (int a, int b) { return a - b; } },
{ "*" , [] (int a, int b) { return a * b; } },
{ "/" , [] (int a, int b) { return a / b; } }
};
call using mp[op](a, b);
You forgot to add memoization, dude!
can i ask the blackboard that u use for visualizing ?
paint 3d on windows, but it looks like its going to be discontinued soon