Decode Ways | Recursion | Memo | Bottom Up | Leetcode 91
ฝัง
- เผยแพร่เมื่อ 20 ก.ย. 2024
- Whatsapp Community Link : www.whatsapp.c...
iPad PDF Notes - github.com/MAZ...
This is the 75th Video of our Playlist "Dynamic Programming : Popular Interview Problems".
In this video we will try to solve a famous and good DP Problem - Decode Ways (Leetcode 91).
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.
Problem Name : Decode Ways
Company Tags : Google, Meta, Microsoft, Uber
My solutions on Github(C++ & JAVA) : github.com/MAZ...
Leetcode Link : leetcode.com/p...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My GitHub Repo for interview preparation : github.com/MAZ...
Subscribe to my channel : / @codestorywithmik
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
Approach-1 Summary (Recursion + Memoization) : The solve function explores decoding possibilities, memoizing results to avoid redundant calculations. The approach considers base cases for index bounds and '0' digits, and recursively calculates decoding possibilities for single and double-digit combinations. The method initializes memoization, sets the string length, and returns the total number of decoding possibilities.
Approach-1 Summary (Bottom Up) : In this approach, we iterate through the string, maintaining a vector t to store the number of ways to decode strings of various lengths. It updates the decoding possibilities based on the current and previous digits, considering valid two-digit combinations. The method initializes the string length n and returns the total number of decoding possibilities.
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
✨ Timelines✨
00:00 - Introduction
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa
Give this guy an Award 🫡❤️
Hats off to such a detailed explanation 🙌
yr aap addictive ho question khud se ho bhi jaaye phir your solution really kuch na kuch extra samjha hi jaata like itna bhi hard nhi sochna tha😊
Netflix ❌
MIK’s Long Detailed Videos ✅
tru
💯
Sir weekly contest ka Qn-3 banado please. Aapse acha koi nahi samjhata.
+1
Weekly Contest 377 Qn - 3
th-cam.com/video/M8WnAIhTjmQ/w-d-xo.htmlsi=U8onTOhsee0T7Q7M
Was able to solve this on my own! Thanks to your previous videos for teaching me the concept.
My implementation:
class Solution {
public:
int dp[101];
int solve(int ind, string &s){
if(ind==s.size()) return 1;
if(dp[ind]!=-1) return dp[ind];
int ans=0;
int num=s[ind]-'0';
if(num!=0){
ans+=solve(ind+1,s);
}
if((num==1 || num==2) && ind
❤️🙏😇
Just completed the video. Bottom Up ka fear bhaga Diya sir apne. Tussi great ho.
Yrr you have such a soothing voice..
Please try in dubbing /RJ roles as well..
And you can continue to post videos as well..
Means a lot ❤️❤️🙏🙏
its request please provide solution and explanation of weekly and biweekly contest questions also.
Weekly Contest 377 Qn - 3
th-cam.com/video/M8WnAIhTjmQ/w-d-xo.htmlsi=U8onTOhsee0T7Q7M
Bhau jis trah se aap samjhate ho mja aa jata hai mai tree diagram toh pohonch gyabtha but yeh conditions banane me problem after this I am feeling confident thank you 🙏
Please check one biweekly contest question,count the number of incremovable subarray,its difficult to understand how to take the approach,plz check it once if possible sir
Noted. Let me check this week only ✌️
@@codestorywithMIK means a lot sir❤️
Amazing explanation
You killed bottom up dude. No one can make tough topics easy like you do.
Very detailed and easy to understand explanation
Glad it was helpful! 🙏🙏😇
Just like my fear of Graph is gone because of your Graph playlist,
My fear of bottom Up DP is slowly going because of you. I came here to see bottom up and you nailed it 🙌🔥
bro i request you to please start making weekly and biweekly contest videos too it will be great helpful and if you start live stream that will be super helpful
Weekly Contest 377 Qn - 3
th-cam.com/video/M8WnAIhTjmQ/w-d-xo.htmlsi=U8onTOhsee0T7Q7M
@@codestorywithMIK thanks bro hope you covered all the questions of contest
Great video 👌
Thank you 😇❤️
Great video
Understood.
Nice explanation
😇🙏
Pura Bawal vaiya 🔥🔥
Sir solved by own top tup approach thanks sir
❤️🙏😇
Just by looking at the logic of recursion from the beginning, I understood your approach. Thankyou so much for clarification bhaiya,
here is my code :
public int numDecodings(String s) {
int n = s.length();
int[] dp = new int[n+1];
dp[n] =1;
for(int i = n-1;i>=0;i--){
if(s.charAt(i)=='0'){
dp[i] = 0;
}else{
int oneDigit = dp[i+1];
int twoDigit =0;
if( i+1 < n && ((s.charAt(i)=='1') || (s.charAt(i)=='2' && s.charAt(i+1)
Sir please contests ke 3rd, 4th questions ki bhi videos banaiye 🙏
Weekly Contest 377 Qn - 3
th-cam.com/video/M8WnAIhTjmQ/w-d-xo.htmlsi=U8onTOhsee0T7Q7M
advance congratulations of 14k+ subscription.
Thank you so much 😀
Thanks for the explantion of tabulation.
in approach 2 (tabulation) on Github
it says time and space as both to be o(n)
but in this way, memoization is more optimal as it has O(n) time and O(1) space
Also, I couldn't understand the approach 3(bottom up 2) and approach 4
//t[i] = ways to decode string of length i
t[0] = 1;
why is there no check if t[0] is '0' or '1' ?
One more thing is that, I always stuggle to identify time complexity in question invloving complex data structure or question which involve recursion or solution. I have learnt time complexity concept multiple times, but they always teach easy snippets to explain, but don't explain how to find time and space in lets say Trie Questions. Any remedy for this would help because I want to learn how you tell the time complexity in one go.
thanks
you're ignoring the auxiliary stack space for memoization part. for the second doubt, for this part //t[i] = ways to decode string of length i. hence t[0] is actually string of length 0 means no string actually. for t[1] is a string of length 1 which might be '0' hence we're checking
❤❤❤
awesome bro
Thank you ❤️🙏😇
❤
Best explanation on
Thank you 🙏😇
Great !!!!
My simple solution :-
class Solution {
public:
int dp[101];
int solve(int idx , string s )
{
if(idx==s.size())
{
return 1;
}
if(s[idx]=='0')
return 0;
if(dp[idx] != -1)
return dp[idx];
//way 1 => take 1 char at time
int count = 0;
count = solve(idx+1 ,s);
//way 2 take substring of size 2 but substr must be < "27"
if(idx< s.size()-1 && s.substr(idx,2) < "27")
{
count += solve(idx+2 ,s);
}
return dp[idx] = count;
}
int numDecodings(string s) {
memset(dp,-1,sizeof(dp));
return solve(0,s);
}
};
I am not able to understand why t[n] = 1.
If s="0" then t[n]=0 how can we assume it will be 1 ?
🔥++
thank you!
i was able to solve dis....till space optimization 😪
Thanku bhaiya ❤
dp[i] -> no. of decode ways till length i
can we solve using this state ? How???
bhai please java ka bhi explain krna video m...:(
Noted 👌
public int numDecodings (String s){
if (s.charAt(0)=='0') return 0;
int n=s.length();
int[]dp=new int [n+1];
dp[0]=1;dp[1]=1;
for(int i=2;i
Space Complexity : O(1)
class Solution {
public:
int numDecodings(string s) {
int n = s.length();
int prev=1,prev2=0;
for(int ind=n-1;ind>=0;ind--){
int curr = 0;
if(s[ind]!='0'){
curr = prev;
if(ind+1
Follow up decode ways 2
Let me check soon 🙏
aazadi ka 75th mahotsav
😅
Thanks 👍
Kya ye question sirf dp se hi solve ho sakta hai
There is one constant space solution.
BUT, if you see, the approach is actually internally using past results (which is nothing but DP only)
Reference - MIK's Github Repo (Approach-4)
class Solution {
public:
int numDecodings(string s) {
int n = s.length();
if(n == 1)
return s[0] == '0' ? 0 : 1;
if(s[0] == '0')
return 0;
int last1 = 1, last2 = 1;
for(int i = 1; i
@codestorywithMIK i want to contribute a qns in leetcode can u help me i have previously contributed a qn to leetcode 9 months back but it is in still pending
Hi there,
Actually i have never contributed on leetcode before. That’s why I am also not sure. But let me check
Amazing explanation