Different Ways to Add Parentheses - Leetcode 241 - Python

[@thepriestofvaranasi]

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.

[@hk254lyt8]

Same bro

[@adityamwagh]

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?

[@NeetCodeIO]

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.

[@chaitanyasharma6270]

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

[@anthonyguerrera191]

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

[@meemee417]

leetcode tags calls everything dp, but i personally think this is more divide and conquer than dp

[@fieworjohn5697]

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.

[@JamesBond-mq7pd]

wow. your solution way more better than in editorial.

[@NeetCodeIO]

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

[@nandanimadhukar]

This problem made me realize that I had gaps in understanding recursion!

[@putopavel]

Another alternative to using lambdas is relying on the operator Python module: import operator operators = {"+": operator.add, "-": operator.sub, "*": operator.mul}

[@satyajit_2003]

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.

[@nOnAme-nc6id]

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.

[@ameyak8401]

base case trick was excellent. i remember using eval on all the n1,n2 was very inelegant in comparison.

[@MP-ny3ep]

Very beautifully coded ! Thank you for the daily problems

[@aadil4236]

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.

[@JeevaParkkavan-d1g]

Hey Neetcode, how could you come up with these approaches? pretty good thing mann

[@rdubb77]

Did being good at leetcode actually help you when working at Google?

[@artem_r]

if you work in algorithms heavy problems, why not? Eg. compression webp

[@takeuchi5760]

Problem solving skills are never wasted.

[@rdubb77]

@@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

[@rdubb77]

@@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

[@ZackWhitbord]

​@@rdubb77 import oriented programming is the best paradigm

[@ihor4256]

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.

[@chaitanyasharma6270]

I can do this in java too with Map

[@chaitanyasharma6270]

Even if you dont know BinaryOperator exists just create your own functional interface

[@chaitanyasharma6270]

@FunctionalInterface interface Operator { int operate(int x, int y); } With this we can do map.get('-').operate(1,2)

[@mohamed44324]

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.

[@DanielDiaz-hm2oe]

What is the time complexity of this solution? I arrived at a different result than what is provided in the LeetCode editorial.

[@pastori2672]

ngl that lambda dict was clean af, i always forget they exist

[@chuckle_pugz96]

this code was sweet like a laddoo

[@TJ-qv8rx]

So elegant!

[@jaatharsh]

thanks again buddy

[@chaitanyasharma6270]

I think there is some repeated work we can then also do some caching based on l+','+r

[@chaitanyasharma6270]

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

[@jalajshrivastava3320]

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?

[@Gojo-hl7iu]

i dont understand the integer conversion base case he added at the end can someone explain

[@rkgk5445]

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.

[@anna-plink]

Memoization could help a little, no?

[@thepriestofvaranasi]

Yupp it does. I actually gave the whole thing to ChatGPT lol and asked it to optimize if possible and it suggested that I add a dictionary to store the sub-problem results.

[@minaFbeshay]

You forgot to add memoization, dude!

[@EliasKibret]

would you please explain how do we know that we have only 3 operators?

[@fieworjohn5697]

It was mentioned in the constraints: "expression consists of digits and the operator '+', '-', and '*'"

[@thepriestofvaranasi]

It's mentioned in the question

[@aadityatripathi8363]

Can anyone tell me how to implement "operations dictionary with the lambda" in c++ ?

[@rkgk5445]

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

[@heisenberg8055]

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);

[@godoftroller4825]

can i ask the blackboard that u use for visualizing ?

[@NeetCodeIO]

paint 3d on windows, but it looks like its going to be discontinued soon

[@isi1044]

Bra