Table of Contents: Messing Around 0:00 - 1:16 The Problem Introduction 1:16 - 2:54 Recursion Tree Walkthrough 2:54 - 8:06 Pruning The Recursion (With Memoization) 8:06 - 10:26 Time Complexity 10:26 - 10:40 Space Complexity 10:40 - 11:22 Yeah 11:22 - 11:38 The solution for this problem as described in the video is in the description.
Hey man, I just really love how you teach the concepts and not the coding. We can find the code in whatever language on LC but this is actually really helping me understand how to get to the answer - keep up the great work! :)
I had a facebook phone interview last week. It's exactly this question!!!!! But I couldn't solve it at that time. I felt really depressed. Thanks for this video! I become more clear about DFS.
I like how you explain the problem/solution without using code in the video. It lets me understand what needs to be done without giving me a bias on how to code a solution when I re-attempt the problem.
Well i must say that you explained the concept of dynamic programming deeply in this video and actually made me realize that how to think from the basic . Thanks !
this is my first video on your channel , i dont know dp , currently i am learning recursion only , man your explanation is outstanding! I love it ,, thank you
Shit, I came up with recursive solution by myself but without tree pruning, realized it was too slow. Then I found your video, thank you for teaching me a valuable lesson!!!!!!!!!
Thanks to show me the recursion approach of this problem. If I had skipped to DP solution , I would never understand the reason behind this problem. Recursion ,then memoization and then DP (Bottom UP approach) is the best sequence. DP is hard and your videos is really making me understand DP. I know that I need practice, practice and practice.
In your solution, "int[] previousAnswers = new int[s.length() + 1];" you don't really need a dp array size s.length() + 1, your answer is at previousAnswers[0] and the length of previousAnswers[] should be s.length(). Love your videos, they are very helpful! :)
Are you sure? Been a while since I wrote the same, I did it hastily. If you are correct and the fix passes test cases, if you open a PR I can merge it in.
Very nice video. So, as per the code, the final answer will be returned by previousAnswers[0] right? Also is there any solution out there that has just recursion and doesn't use DP? Would be of great help. I couldn't find any. I know that it would be inefficient, but wanted to first learn that and then jump into DP problems.
Yeah, and if it didn't cache answers nothing would change except the time complexity would simply become worse. All caching does is prune the recursion tree.
@@BackToBackSWE thanks for the clarification. Basically arr[i] = arr[i+1] (+ arr[i+2] if 2 chars are valid) Also was wondering if the question was to print all the possible decoded ways instead of just the count, would it be possible to solve it in under O(n^2) ? I tried, an iterative solution using a map and char append strategy, but couldn't optimize it.
Hey , I am new to DP. What I thought is to recurse all the digits at each node, But I didn't get that we can make choice that we can pick either one element / two element. Need some help regarding how did you arrive to that decision. . Thank u SO much. Your videos are awesome.
Although the recursive solution is straight-forward, it can only cope with strings of length ~500 in Python. Once it gets longer, there will be a RecursionError.
Hey Benyam, I'm not able to figure out the subproblems for new DP questions. Do I just practice more and more problems to see a pattern amongst these problems? Because I can't afford to loose time figuring out these sub problems in a coding challenge with limited time...
Back To Back SWE yes you did. Instead of being anxious not able to think of sub problems, I realize if I patiently keep pushing myself, soon I will be able solve these problems easily...
Great explanation, only advice would be to go in a bit more explanation into what the memo-schema looks like. Are we storing the index at a certain point as the key and the value is the number of ways you can decode?
Hi Ben, I know you mentioned "Space Complexity @10:20 and @10:40 - 11:22." But can you explain why we use Space Complexity - O(n) on the call stack - in the brute force approach?
There is no link to the code in your description, please add it. In your video if you explain with the code by dry run then the intuition makes more sense
Added it to the first 100 video list. That question is very good. It looks like a Facebook question I saw a while back. Looks to me like backtracking but I'll see when I do my notes for it.
Say I want to store all the possible decodings in a string array. can we still do it in O(n) time? if so, what do I need to do to store the decodings in a recursive approach?
Happy Holidays 🎉 You're the best! We'd love to offer you a 40% Off our exclusive lifetime membership just use the code CHEER40 - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=CHEER40
@@BackToBackSWE well hope ur transition is smooth and as u say u will make this channel one of the largest resource for software engineering interviews!!
The same code in Python except for a minor change. def numDecodings(string): cache = [-1 for k in range(len(string)+1)] return numDecodingsHelper(string, 0, cache) def numDecodingsHelper(string, decodePointer, cache): if decodePointer >= len(string): return 1 if cache[decodePointer] > - 1: return cache[decodePointer] totalWays = 0 if (decodePointer + 1)
sort of? For ip decomposition we use pruned recursion to generate all possible decompositions (I'm not sure how we could use dynamic programming for that). For this problem we do recursion as well, pruning our recursion tree along the way down.
It will be 0. We cannot decode this string. Since in order for a string to have zero, it must be preceded by a 1 or a 2.( 10 and 20 are the only valid codes possible)
i've following u since months now. i really want to buy you subscription, but i m not that sound financially... is there any discount i can get ?? u r great really.......
Happy Holidays 🎉 You can find the code on our platform andmany other questions! We'd love to offer you a 40% Off our exclusive lifetime membership just use the code CHEER40 - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=CHEER40
![ง้อ (ALRIGHT) - FOURTH Prod. by URBOYTJ [ OFFICIAL MV ]](http://i.ytimg.com/vi/Qs8ZeV6Dqj8/mqdefault.jpg)
Table of Contents:
Messing Around 0:00 - 1:16
The Problem Introduction 1:16 - 2:54
Recursion Tree Walkthrough 2:54 - 8:06
Pruning The Recursion (With Memoization) 8:06 - 10:26
Time Complexity 10:26 - 10:40
Space Complexity 10:40 - 11:22
Yeah 11:22 - 11:38
The solution for this problem as described in the video is in the description.
Where is the code?
@@dhondipranav3721 same question
Where is the code?
where is the code
Where is the code?
Hey man, I just really love how you teach the concepts and not the coding. We can find the code in whatever language on LC but this is actually really helping me understand how to get to the answer - keep up the great work! :)
Sure, live and prosper
The recursion code is not in the description. :(
Please provide the link.
Thanks
I had a facebook phone interview last week. It's exactly this question!!!!! But I couldn't solve it at that time. I felt really depressed. Thanks for this video! I become more clear about DFS.
nice, keep it up
weird for a phone interview
lollllll, the intro.
I'm a fool
@@BackToBackSWE The reaction to the CTC break-up was hilarious!
@@akhileshsingla3212 ye
@@BackToBackSWE lol no, you're cute xD
Your way of explaining first the problem with the O(2n) approach then going to the optimised one really helps a lot. Thanks for your rich videos. :)
when you just dropped the time complexity from exponential to linear by pruning the tree .. BRAINS OUT !!
Amazing, really helpful!
sure
I like how you explain the problem/solution without using code in the video. It lets me understand what needs to be done without giving me a bias on how to code a solution when I re-attempt the problem.
Nice
Dude your intros are the best lol. Thanks a lot for your videos!
I know. I'm just messing around since these videos are generally boring to watch.
Really Really good man. Understood the solution in depth. The Recursion tree helped a lot. Keep up the good work.
great
Well i must say that you explained the concept of dynamic programming deeply in this video and actually made me realize that how to think from the basic . Thanks !
great.
Exactly what I was looking for ... a recursive solution. Thanks man.
you're welcome, the code is in the description if you haven't already found it
@@BackToBackSWE where ?
The way u explain the logic using recursion tree is superb.... Thank you
sure
You have a great knack for explaining these problems. Fantastic Work!
im trying
@@BackToBackSWE Came back to this problem and video again after 2 years. Just saw your reply. You're still nailing it in 2021 :)
this is my first video on your channel , i dont know dp , currently i am learning recursion only , man your explanation is outstanding! I love it ,, thank you
great and great.
I've seen a few videos until now, and I can say your explanations are always better than others😊Thank you always. And I also love your clear voices!
thanks
This explanation is one of the most intuitive explanations i have found on the internet...KUDOS!!!
Thanks!
Hey! Great explanation but where's the code for this question??? I can't find it in the description.
Shit, I came up with recursive solution by myself but without tree pruning, realized it was too slow. Then I found your video, thank you for teaching me a valuable lesson!!!!!!!!!
sure
I am just wondering there code is ? I didn't find anything in the description
Thanks to show me the recursion approach of this problem. If I had skipped to DP solution , I would never understand the reason behind this problem. Recursion ,then memoization and then DP (Bottom UP approach) is the best sequence. DP is hard and your videos is really making me understand DP. I know that I need practice, practice and practice.
ye
It's Aug, 2022 and I am still loving these videos! Amazing work! 🙏
Beautifully explained .Thanks much
ye
In your solution, "int[] previousAnswers = new int[s.length() + 1];" you don't really need a dp array size s.length() + 1, your answer is at previousAnswers[0] and the length of previousAnswers[] should be s.length(). Love your videos, they are very helpful! :)
Are you sure? Been a while since I wrote the same, I did it hastily. If you are correct and the fix passes test cases, if you open a PR I can merge it in.
@@BackToBackSWE Yes i have verified it. Created a PR for you.
@@NJTROJAN ok
Man took a launch code assessment test kick my butt.
dang
Very nice video.
So, as per the code, the final answer will be returned by previousAnswers[0] right?
Also is there any solution out there that has just recursion and doesn't use DP? Would be of great help. I couldn't find any. I know that it would be inefficient, but wanted to first learn that and then jump into DP problems.
Yeah, and if it didn't cache answers nothing would change except the time complexity would simply become worse. All caching does is prune the recursion tree.
@@BackToBackSWE thanks for the clarification.
Basically
arr[i] = arr[i+1] (+ arr[i+2] if 2 chars are valid)
Also was wondering if the question was to print all the possible decoded ways instead of just the count, would it be possible to solve it in under O(n^2) ? I tried, an iterative solution using a
map and char append strategy, but couldn't optimize it.
@@chandanhegde4923 I'm not sure, I'd have to think about this.
Thank youuuu so much for this video!!!!
i was using backing tracking for this and got TLE, storing the solution is great idea to reduce time complexity . Thanks
Loved your introduction, :) your explanation is great as always...
sure
The best explanation I have heard ...thank you 😊
but where's the code?
my soul lights up when he says "expression"
lmao soul
Hey , I am new to DP.
What I thought is to recurse all the digits at each node, But I didn't get that we can make choice that we can pick either one element / two element.
Need some help regarding how did you arrive to that decision.
.
Thank u SO much. Your videos are awesome.
Thanks and the idea is we follow the "paths" of decomposition. Path items can only be single or 2 digit numbers.
Although the recursive solution is straight-forward, it can only cope with strings of length ~500 in Python. Once it gets longer, there will be a RecursionError.
ok
Stack overflow error ??
Hey Benyam, I'm not able to figure out the subproblems for new DP questions. Do I just practice more and more problems to see a pattern amongst these problems? Because I can't afford to loose time figuring out these sub problems in a coding challenge with limited time...
Yeah, you just have to do many problems and read textbooks. Which makes dp problems stupid.
Thanks! That really helped
@@ak_allday__ Did it? I didn't say much.
Back To Back SWE yes you did. Instead of being anxious not able to think of sub problems, I realize if I patiently keep pushing myself, soon I will be able solve these problems easily...
Amazing clean at easy to understand code. I also like the intro.
haha yeah
where is the code have u found out
Anyone watching this in 2021?
Where is the solution in the description?
cant find the solution in description... can you please check ?
The repository is deprecated - we only maintain backtobackswe.com now.
Very good explanation.
thanks
bro you're a beast. subscribed!
ye
Great explanation, only advice would be to go in a bit more explanation into what the memo-schema looks like. Are we storing the index at a certain point as the key and the value is the number of ways you can decode?
yes
Hi Ben, I know you mentioned "Space Complexity @10:20 and @10:40 - 11:22." But can you explain why we use Space Complexity - O(n) on the call stack - in the brute force approach?
If we decompose 1 char at a time it is string length in call stack frames created
But where is the code in description?
The repository is deprecated, we only maintain backtobackswe.com now.
What an introduction!!
lol
There is no link to the code in your description, please add it. In your video if you explain with the code by dry run then the intuition makes more sense
The repository is deprecated - we only maintain backtobackswe.com now.
I love your channel a lot!
Recursion and algorithm is clear but I don't understand how to implement dynamic programming in it? Any suggestions?
Got it and the DP part is just caching the answes to substrings in a 1D array
Great video! Having trouble finding the iterative solution video
This is good content please do "expression-add-operators" next
Added it to the first 100 video list. That question is very good. It looks like a Facebook question I saw a while back. Looks to me like backtracking but I'll see when I do my notes for it.
Say I want to store all the possible decodings in a string array.
can we still do it in O(n) time? if so, what do I need to do to store the
decodings in a recursive approach?
Can you elaborate on the approach you are thinking of?
thanks@
sure
Thank you so much for the videos!
It is nothing. Just keep learning and be the best you can be. That is why I am here.
You are the best!
Happy Holidays 🎉 You're the best! We'd love to offer you a 40% Off our exclusive lifetime membership just use the code CHEER40 - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=CHEER40
just wow.. keep it going buddy
ok
Loved that opening zinger.
lol, old video, my bad. new year new me
Can you please share the code?
Is there a way to do it in a bottom-up approach instead of top down?
Yeah, Leetcode has a lot of them just iteratively going through the string
Question my brother! Is perfecting interview questions the goal?
What haha
Where is the code you said in the description????
on our website
What will be the iterative solution to this problem
leetcode.com/problems/decode-ways/discuss/30358/Java-clean-DP-solution-with-explanation
Hahahah that opening feels like the robot Mark coldly discounted all your work experience like just that
oh hahaha that was whack - old video no one watched then
the github link doesnt exist. Code is missing. but I like the conceptualization of the problem. facing issue with pruning the tree
ik
why did you stopped uploading videos dude!!!.your videos are really helpful
we are undergoing organizational changes and I'm at a life transition point
@@BackToBackSWE well hope ur transition is smooth and as u say u will make this channel one of the largest resource for software engineering interviews!!
The same code in Python except for a minor change.
def numDecodings(string):
cache = [-1 for k in range(len(string)+1)]
return numDecodingsHelper(string, 0, cache)
def numDecodingsHelper(string, decodePointer, cache):
if decodePointer >= len(string):
return 1
if cache[decodePointer] > - 1:
return cache[decodePointer]
totalWays = 0
if (decodePointer + 1)
nice
Super explanation 👍👍
The intro made my day! xD
Thank you!
sure
So where is the example of memorization code?
Haha that's gonna be me next Tuesday
we are slaves to the system
Thanks for the video! Where can I find the code?
repository is deprecated - we only maintain code on backtobackswe.com now - it is what we are building
Where is the code bro in description?
isnt it similar to ip decomposition.. Can we apply memoization to ip decomposition too??????
sort of? For ip decomposition we use pruned recursion to generate all possible decompositions (I'm not sure how we could use dynamic programming for that). For this problem we do recursion as well, pruning our recursion tree along the way down.
What is the determination of a character is decodable? What is the rule ?
wym?
I don't see any code in the description
We only maintain code on backtobackswe.com
So So entertaining ahahah
sorry, old video. I had 7,000 subs when this was made I believe. forgive it.
@@BackToBackSWE No worries it is a good one :) Was Like a mix between Netflix and Udemy all together :) Keep it up!(Y)
This intro is fire bruh lol
What will be the answer for "01"? And How can you please explain?
I believe 1, I did this a long time ago, etc.
It will be 0. We cannot decode this string. Since in order for a string to have zero, it must be preceded by a 1 or a 2.( 10 and 20 are the only valid codes possible)
@@rachitsaksena232 Thanks!
I am confused.. Take string "2263"
I can have 2, 22, 26 and 3, can't I. So why is the answer 3 ?
i've following u since months now. i really want to buy you subscription, but i m not that sound financially... is there any discount i can get ??
u r great really.......
Hi we dont offer any currently
Code is missing
ok
Where can i find the code(your code) related to this?
The repository is deprecated and we only maintain backtobackswe.com now.
Great vid
thx
Can you please paste an alternate link for the code ? It says page not found
yeah it is broken
@@BackToBackSWE could you send the code to me please. ?
I'm preparing for interviews and i really need it !
mrvaibhavrastogi@hotmail.com
where is code, u say its in description ?
The repository is deprecated - we only maintain backtobackswe.com.
I didn't know Chris Paul teaches programing
where is the code of this problem?
The repository is deprecated - we only maintain backtobackswe.com now.
Where is the link to code? I can't find it.
The repository is deprecated - we only maintain backtobackswe.com now.
actually where is the code ??
i didn't found it
The repository is deprecated - we only maintain backtobackswe.com now.
I have noted that in description box ou write *Tuschar Roy* However the correct name is *Tushar Roy*
my b, I love all people
There's no solution in the description?
Happy Holidays 🎉 You can find the code on our platform andmany other questions! We'd love to offer you a 40% Off our exclusive lifetime membership just use the code CHEER40 - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=CHEER40
Code link is broken. Please fix the same.
ik
I don't see code in description.. can u post it?
The repository is deprecated - we only maintain backtobackswe.com now.
@@BackToBackSWE oh okay👍
Lmao! Very Clever!
hey, what's up, Doc?
@@BackToBackSWE LOL You Know... Wabbit ho's!
Where the hell is the code then?
Hi is there an implementation in Python?
We only maintain code samples on backtobackswe.com (paywall) now.
@@BackToBackSWE Thank you, will keep in mind :)
Can you do 301. Remove Invalid parentheses please?
hey, I would but busy with school and other things
@@BackToBackSWE If you'd get time, please make one. Thanks
@@jaskaransethi2000 I don't have the time I think
great intro haha
sorry - old video- no one watched
This is string decomposition, ofcourse with some pruning. right ?
Yes. The decomposition only follows a valid path that a proper decoding can follow. Correct.
where's the link to the code?
The repository is deprecated - we only maintain backtobackswe.com now.
@@BackToBackSWE meaning I need to buy the product ? XD