Total Ways To Decode A String - Recursive Dynamic Programming Approach ("Decode Ways" on LeetCode)
Vložit
- čas přidán 27. 07. 2024
- Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Question: A message containing letters from A-Z is being encoded to numbers using the following mapping: 'A' - 1 'B' - 2 ... 'Z' - 26. Given a non-empty string containing only digits, determine the total number of ways to decode it.
Examples:
1
Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).
2
Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
Complexities:
n is the total digits in the input string
Time: O( n )
Memoization prunes our recursion tree and we will do a linear amount of work to solve the problem.
Space: O( n )
We will need to store the answer to up to n subproblems that we will need to calculate
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech - Věda a technologie
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
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. :)
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.
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
The way u explain the logic using recursion tree is superb.... Thank you
sure
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 ?
Really Really good man. Understood the solution in depth. The Recursion tree helped a lot. Keep up the good work.
great
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 :)
when you just dropped the time complexity from exponential to linear by pruning the tree .. BRAINS OUT !!
Amazing, really helpful!
sure
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
I am just wondering there code is ? I didn't find anything in the description
Loved your introduction, :) your explanation is great as always...
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
i was using backing tracking for this and got TLE, storing the solution is great idea to reduce time complexity . Thanks
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.
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
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.
It's Aug, 2022 and I am still loving these videos! Amazing work! 🙏
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
Hey! Great explanation but where's the code for this question??? I can't find it in the description.
Amazing clean at easy to understand code. I also like the intro.
haha yeah
where is the code have u found out
Beautifully explained .Thanks much
ye
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
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?
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.
I love your channel a lot!
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...
What an introduction!!
lol
Man took a launch code assessment test kick my butt.
dang
bro you're a beast. subscribed!
ye
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.
Where is the solution in the description?
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
Loved that opening zinger.
lol, old video, my bad. new year new me
This explanation is one of the most intuitive explanations i have found on the internet...KUDOS!!!
Thanks!
Can you please share the code?
The best explanation I have heard ...thank you 😊
Question my brother! Is perfecting interview questions the goal?
What haha
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
Where can i find the code(your code) related to this?
The repository is deprecated and we only maintain backtobackswe.com now.
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
Great video! Having trouble finding the iterative solution video
Thank you!
sure
the github link doesnt exist. Code is missing. but I like the conceptualization of the problem. facing issue with pruning the tree
ik
just wow.. keep it going buddy
ok
my soul lights up when he says "expression"
lmao soul
cant find the solution in description... can you please check ?
The repository is deprecated - we only maintain backtobackswe.com now.
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.
Where is the code bro in description?
but where's the code?
Very good explanation.
thanks
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
But where is the code in description?
The repository is deprecated, we only maintain backtobackswe.com now.
I am confused.. Take string "2263"
I can have 2, 22, 26 and 3, can't I. So why is the answer 3 ?
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
The intro made my day! xD
You are the best!
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.
What will be the iterative solution to this problem
leetcode.com/problems/decode-ways/discuss/30358/Java-clean-DP-solution-with-explanation
Where is the link to code? I can't find it.
The repository is deprecated - we only maintain backtobackswe.com now.
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 ??
Super explanation 👍👍
So where is the example of memorization code?
Where is the code you said in the description????
on our website
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.
This is string decomposition, ofcourse with some pruning. right ?
Yes. The decomposition only follows a valid path that a proper decoding can follow. Correct.
I don't see any code in the description
We only maintain code on backtobackswe.com
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
actually where is the code ??
i didn't found it
The repository is deprecated - we only maintain backtobackswe.com now.
What is the determination of a character is decodable? What is the rule ?
wym?
Great vid
thx
Haha that's gonna be me next Tuesday
we are slaves to the system
Code link is broken. Please fix the same.
ik
where is the code of this problem?
The repository is deprecated - we only maintain backtobackswe.com now.
where is code, u say its in description ?
The repository is deprecated - we only maintain backtobackswe.com.
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
github link doesn't work :-(
ik, will fix
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!!
This intro is fire bruh lol
cant find the solution
why you remove code link ????
The repository is deprecated - we only maintain backtobackswe.com
I don't see code in description.. can u post it?
The repository is deprecated - we only maintain backtobackswe.com now.
@@BackToBackSWE oh okay👍
Git link seems to be broken
ik
The code link is broken
got it thanks
Code is missing
ok
thanks@
sure
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!
Where is the solution?
Hi is there an implementation in Python?
We only maintain code samples on backtobackswe.com (paywall) now.
@@BackToBackSWE Thank you, will keep in mind :)
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
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
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
Where the hell is the code then?
github link does not work!
ik!
@@BackToBackSWE could you please add it?
where's the code?????
The repository is deprecated - we only maintain backtobackswe.com now.
where is code?
The repository is deprecated - we only maintain backtobackswe.com now.