Decode Ways
Vložit
- čas přidán 5. 02. 2019
- For business inquiries email partnerships@k2.codes My Desk Setup
Desk - bit.ly/3jfY195
Chair - amzn.to/2O9TM3r
Monitor - amzn.to/3rcSHGa
Webcam - amzn.to/2NUmwgi
Desktop - amzn.to/3tiySPL
Laptops - amzn.to/3aRoN3Z
iPad - amzn.to/2LlJzzJ
Keyboard - amzn.to/3jfbxdd
Mouse - amzn.to/36ElWtT
Wrist Rest - amzn.to/3trrHF4 (pls don't buy this)
Mouse Pad - amzn.to/2Myz2lt
Microphone - amzn.to/3atNyTA
Lamp - amzn.to/3jjfZYp
Headphones - amzn.to/3tvr0KU (new model)
Headphone Hook - amzn.to/3tr8uTC
Blue Light Glasses - amzn.to/3cDVUdK
Wireless Charger - amzn.to/39LY1uu
Keyboard cable - amzn.to/2O5p2R5
Mic arm - amzn.to/3cECZj8
Audio interface - amzn.to/36HdWIi
Cloudlifter - amzn.to/36VO6kf
Laptop dock - amzn.to/2O2DsBw
Motherboard - amzn.to/3rkiWuA
Solid state - amzn.to/3rk5vuo
CPU cooler - amzn.to/3tnwwPA
CableMod - amzn.to/3tqbtM8
CPU - amzn.to/3auG1ns
Power supply - amzn.to/3trsAxo
RAM - amzn.to/39JZcuf
Designing Data-Intensive Applications - amzn.to/2YK4ek1
Clean Code - amzn.to/3txqfB5
Meditations - amzn.to/3cDa4fi
SOCIAL
----------------------------------------------------------------------------------------------------------------
Support me on Patreon: / kevinnaughtonjr
Follow me on Twitter: / kevinnaughtonjr
Follow me on Instagram: / kevinnaught. .
Follow me on GitHub: github.com/kdn251
MUSIC
----------------------------------------------------------------------------------------------------------------
best boy in ballincollig by ｊａｒｊａｒｊｒ
/ best-boy-in-ballincollig
#coding #interviews #softwareengineering #dynamicprogramming Discord: bit.ly/K2-discord - Věda a technologie
What kinds of videos can I make to help you guys?
(Suggestion)Maybe you could do this: Choose a topic and give an explanation on it(like how to approach it and what are the best ways to solve it with their corresponding complexities) and later solve one question on that particular topic(kind of hands-on tutorial).
And yeah, please continue this coding series :)
God bless you man :)
@@mayankdevnani894 Awesome idea, I'll see what I can do with that :). I will continue these videos don't worry thank YOU for the support!!!
what kinds of the problem need to use dp? because when I look at a problem I don't realize when should I use dp and how to use dp. I only know how to solve some dp problem bc I remember the way of solving them.
Sort your video playlist according to easy, medium, hard.
BTW, I loved your videos a d subscribed.
Explaining recursion in depth including what happens in each stack frame and how not to lose track when debugging/tracking the calls. Also, I have noticed that each kind of recursive problem applied on Strings, Arrays or Trees have a recursive pattern. If you can help identify what patterns it boils down to or is an extension of.
@kevin, it would be really helpful if you first explain the approach and then start the implementation, that really helps us in getting the intuition behind the code.
that's right. hard to follow without board explaination
@@divyadhaipullay5047 shutup dumb girl... like all girls u r dumb
Still can't wrap my head around why a string of length 0 has one way to decode it
If there's nothing in the string, the only way to decode it is by not decoding it. Which counts as one way.
@Surb Singh 0 decode into 0 ways. look at his ternary condition. If the single digit is a 0, assign dp[1] = 0 and return the last index of dp which is 0
@@MonsterhunterFTWWTF Why 1, why not 0 (if you cannot decode it)
@@ayusharora2019 I found this comment by Nikhil Sharma - see this
why dp[0] = 1 :
Back to basics - permutations and combinations:
Combinations of len(n) is n!/r!(n-r)!
(Even if r =0(min))
n!/r!(n-r)! = 0!/0!*0! = 1
if this is using small problem to solve larger problem, could you use recursion as well? what would the solution using recursion look like?
Hey thank you so much for this video, really helpful. I'm just having some trouble understanding why when you add to the twoDigits subproblem you add dp[i-2]. I get that it has to do with the fact that it's 2 digits, but if you could explain with other words that'd be great, thank you!
For one digit, we go back 1 to get previous value and add it to dp[i]
In case of two digits, we consider the last two digits as ONE value, so we go back 2 to get previous value and add to total sum of dp[i] which is already dp[i-1] currently. so basically we add twice for two digits (once for number of ways to decode considering two digits as two numbers and other for number of ways to decode of two digits as single number).
if string is "126" dp[] = 1 1 2 3
dp[0] = 1
dp[1] = 1
dp[2] = 2 -- initially 1 as we consider 1,2 for two letters( dp[1] ) and then add dp[0] as two digit is 12 so we can consider it as single letter
dp[3] = 3 -- (2+1 same logic as dp[2])
How come your oneDigit variable is taking the current character? s.substring( i-1 , i ) for i=2 will give the character at place 1, right? startIndex is inclusive and the end index is exclusive. Is my understanding wrong? How come your code is working?
While updating dp[i] for single digit, we don't need to do dp[i] += dp[i-1] instead dp[i] = dp[i-1] works. Because dp[i] is already empty at this point.
Great explanation Kevin. Thanks
what gain are you getting from this optimization?
dp[0] = 1 - How? I could not understand. The string is empty and it should be zero right?
I didn’t understand why do we need to store the running total in an array to incur storage cost of O(N) Wouldn’t it be more efficient to have a local variable (say count or something) that maintains running total?
Because he just parroted the answer from somewhere. He didn't explain anything. This explanation was: " I'm just typing this code and it works!"
The array is not there to act as the "running total", but as a cache. You are computing the new result based on the value of the old result. The array acts like a cache. Number of ways to decode string of length 3 is cache[2] (string of length 2) + cache[1] (string of length 1). Number of ways to decode string of length 4 is cache[3] + cache[2] and so on.
You can use more variables, but the solution would probably look less clear.
@@dmitrysamoylenko6775 I agree, he barely goes into actual explanation. Like diagrams, drafts, intuition, walkthroughs.
how did you come up with the intuition behind this problem
Hey Kevin, What software do you use to create your videos?
What software do you use for the video overlay?
And for all who worry why dp[0] = 1 :
Back to basics - permutations and combinations:
Combinations of len(n) is n!/r!(n-r)! (Even if r =0(min))
= 0!/0!*0! = 1
Then how da fk can dp[1] be 0 but not dp[0]
@@bumq5514 now here dp[1] is dependent on first character of String and it's given in ques we don't have any mapping for '0', so its value will be 0 in that case. This string 0 and choosing nothing from nothing(0) are different.
Your explanations are THE BEST.
Please go on posting more such solution videos with such great explanations
thanks for the help! I realized that this is a fibonacci sequence, so no need for O(n) space
why dp[0] = 1, if there is no string number of ways should be 0 right?
is it necessary to check for 0 at the start? The problem states that the array consists of a string of 'A'-'Z' encoded as number sequences. If you check for 0 at the start - which should be impossible - then wouldn't you also have to check for zero elsewhere, e.g. "2305" which would make 2 interpretations of the string invalid - 0 & 30. And then you'd have to indicate failure which isn't mentioned in the original problem description. Anyway, thanks again for another extremely well-explained solution
what happens if the twoDigits have a leading zero? such as 02? The string 102 returns 3 but how does it represent 0 alphabetically
102 can be decoded 1 way: 10, 2. You cannot decode it as 1, 02.
Thanks, I have watched a few videos for this problem. this one is nicely explained and easy to understand
much better explanation than those I found in the discussion section.
I'm struggling to understand why dp[0] = 1; if the string is empty. If string has a length of 2, such as the number 10, it fetches dp[0] instead of its own merit
There is always a way to decode an empty String and that is the only way hence we take it as 1.
There will never be an empty string. The problem stated that the input is a non-empty string.
@@codearabawy What if the problem removes the restriction of the empty string then what will be dp[0]??
How to know when to use bottom-up approach for a problem?
Practise
For Facebook interviews, do you suggest doing the top Facebook questions or all questions tagged with Facebook? I'm actually unsure of the difference.
As for videos, more videos with dynamic programming and recursion would be great!
Thanks for the input Neal I'll try to add more videos with those topics. Hmmm it's funny because I've asked myself that before but I guess it's best to do both if possible...otherwise, I think if you choose Facebook from the company tags you'll be able to see questions within a certain time period like questions that have been asked in the last 6 months, 1 year etc if that's helpful?
@@KevinNaughtonJr would you prioritize the top ones if you could only do one list? I've done most of the top ones but want to get through the list without rushing it.
@@nealpatel7696 I think either one is fine honestly (I think they're pretty similar in terms of questions?). Lmk if you have any other questions :)
I still had trouble understanding it. Used the debug tool in leetcode to go through it, and it made sense.
Thanks for explanation. I was stuck at this problem. But now I know how to do this question.
I came across a variation of this problem where a --> 0, b--> 1 and so on. How to work this variant ?
ip:- 007 expected op = 1
ip:- 200 expected op = 2
ip = 100200300 expected op = 4
Following seems to work:
def numberOfSequences(input_string):
dp = [0]*(len(input_string)+1)
dp[0] = 1
dp[1] = 1
for i in range(2, len(input_string)+1):
oneDig = int(input_string[i-1:i])
twodig = int((input_string[i-2:i]))
dp[i] += dp[i-1]
if twodig >= 9 and twodig < 26 :
dp[i] += dp[i-2]
return dp[len(input_string)-1
Hello Kevin, great tutorial up there, but I am unable to pass "20" as testcase for above solution.
Vivek Panchal if you’re having trouble with problems like this check out The Daily Byte! thedailybyte.dev/
Not able to understand why we are doing dp[i] += dp[i-2]?? The way I understood the solution is that dp[0] is number of ways to decode input of length 0 and its value is 1. Same way dp[1] is number of ways to decode input of length 1 and its value is 1. So building on these base cases if we have 12 as input - we take either 1 or 2 and since its 1 digit we take value of dp[1] which is 1. moving on we consider both 12 which is a single entity but for this this why we are going back to dp[n-2] which is dp[0] which is number of ways to decode input of length 0? Please explain in layman terms if possible.
Got it for Cisco SDE 2021 assessment
Dynamic programming where for lopp can be used - bottom-up problem
I was trying to solve this problem without DP and my code is huge and macaroni level with all the if/else conditions...LOL... your code looks clean and simple, I like it. Thanks for sharing it! 👍
Thank you and anytime! Don't worry about it these questions are hard just keep practicing!!!
@@KevinNaughtonJr This code wont work for the case s="10"
@@amulyadubey3637 it does work on all cases, you might have a bug in your code.
Thanks for explaining so well :)
Why is dp[0] = 1, shouldn't the ways to decode a string of length 0 be 0?
Hey Anthony, good question! I definitely found it confusing at first, but the way I like to think about it is there's no decoding necessary to decode a string of length 0...so the 1 way to decode it is doing nothing (i.e. the decoding of an empty string is an empty string). Hopefully that makes at least a little bit of sense? Otherwise for dp[0] = 1 in this problem and others I think about how the power set in math contains the empy set (sorry to bring in math). Not sure if they're great parallels but that's what my mind thinks of anyways. If anyone else has better explanations I'd love to hear them. I hope that helps Anthony!
What I would say, if you don't initial it as 1. This code won't calculate properly for the twoDigits case . Thinking the input 12, it will return 1 but it should be 2.
@@xianfuzheng8250 Kevin's code does return 2 for input 12.
@@jayshekarharkar8119 Xianfu saying if dp[0] is not 1, 12 won't return 2. I'm also confusing why dp[0] is 1, according to dp[i] is the number of ways to decode a string of length i. dp[0] should not be 1. But Kevin gives a good example, sometimes we have to define some special cases, like in math 2^0 = 1. Thanks, Kevin.
@@KevinNaughtonJr yeah the concept comes from theory of computation that even to accept an empty string we require 1 state in DFA,NFA.
How come dp[0] = 1; is isn't 0? string is empty and logically zero decoding. Can someone explain?
You are really great at explaining the problems. I wish you would do more Leetcode questions . Thank you :)
Thank you so much for the kind words :) don't worry I'll keep the LeetCode videos coming and thank you so much for your support!!!
Thanks for the video! If I see this on a real interview, would it be better to tell them the recursive way first and then explain the dp way?
That's definitely a good idea! I think during interviews it's a good idea to offer multiple possible solutions and choose one after discussing that particular solutions benefits! Great question!
Love your explanation!
If there is no way to decode a string of length 0, shouldn't dp[0] = 0 instead of dp[0] = 1 ?
this trips me up too
When he starts moving toward the submit button and jams start playing..... You know it's going to pass.
Thanks. It was so hard to understand in leetcode solution and you explained it easy way.
how is it dP[0] =1 for a string length of 0 there is no ways to decode , shouldnt it be 0?
I really like his voice ton when speaking. :)
I don't get why you check if the first character is "0". What happens if the "0" occurs somewhere else? Why only check at the index 0?
What sort of questions/ problems can we expect for Data Engineers?
You have some wicked music taste!
Why is it that on line 10, its dp[i] += dp[i-1], wouldn't dp[i] = 0 and hence dp[i] should be = dp[i-1] if oneDigit >= 1 else 0
Those intros get me hyped. Great music selection.
Jude Ankrah the music is key
Does anyone understand why dp[0]=1 ????
For 101
the first digit is 1 second is 10 and again 1
it gives me 2 possibilities. (Mistake at the conversion)
i have a hard time understanding 1) dp[0]=1, the speaker says there is one way to decode it, so 1. This does not quite make sense to me, as s="0", the answer should be 0, so "no way" to decode it. 2) i
For twoDigit why we are doing dp[i]+= dp[i-2]??
coz for twoDigit, we are considering i and i-1 which means that if we have XYZ and we are currently looking at YZ, then if YZ is valid, then it serves as one entity rather than two separate entities...Hence, we are going to add the number of ways to decode TILL "Y" which would be dp[i-2]
we are finding two possible cases with every iteration,
Case 1: single digit
Case 2: two digit
if single digit is valid, update dp[i]
if two digit is also valid, update dp[i] but, dont forget case1 was also valid so we have to do dp[i] + dp[i-2].
Hope it makes a little sense.
The problem with this problem is to how to understand the problem not how to solve the problem .
There is no way you can decode a string of length 0, so shouldn't it dp[0] be 0?
starting was lit
Came here looking for a solution , but instead, my heart melted seeing the way Kevin lighted up when his girl passes the camera
SHE'S THE BEST!!!!
Are you related to Aravind Kejriwal?
Watched the video and read through some of the comments about dp[0] = 1...yeah still makes no sense lol. Yikes.
Kevin Naughton Jr. I think single variable is enough to handle result.
If there is no way to decode an empty string, then shouldn't it return 0?
nice one..!
I can't figure out why this doesn't work in C++. Like, your same code is not even close to being right on C++. Ugh
Ah man the DOOM in the inros and outros i s making this my fav channel
Possible to do it with stack
Becoz I am having a approch with stack
why is dp[0] = 1 ? you said there is no way to decode empty string, so no way = 1 ?
It only has one solution therefore is one
We do not need a DP array we could use the two pointer and one temp pointer for the calculation
int count1 = 1;
int count2 = 1;
for(int i = 1;i0){
count += count2;
}
if( dd>=10 && dd
This works, but you also need to add the condition if(s[0] == '0') return 0; otherwise it fails for the input "0" as it will return count2=1
@@misoren9645 yeah thanks
Can anyone please explain why we are doing :
dp[i] += dp[i-1]; // In the first if statement.
and
dp[i] += dp[i-2]; //In the second if statement.
Thanks.
I am also struggling 😔😣
In python
class Solution:
def numDecodings(self, s: str) -> int:
dp = [0]*(len(s)+1)
dp[0] = 1
dp[1] = 1 if s[0]!='0' else 0
for i in range(2, len(s)+1):
if 1
Why does this problem have so many dislikes on leetcode?
classic fibonacci series
Please try to make videos on questions from geeksforgeeks
I don’t get why when the twoNumbers is valid we need to add the ways to decode the n-2 :(
For one digit, we go back 1 to get previous value.
In case of two digits, we consider the last two digits as ONE value, so we go back 2 to get previous value.
if dp[0] = 1, shouldn't then dp[1] = 2?
dp[1] = number of ways to decode a number at index 0, which can be number zero (invalid, since A maps to 1 and not zero, so dp[1] = 0, or 1 thru 9 -- a valid number, so dp[1]= 1.
If there is no way to decode an empty string, why would dp[0]=1 ?? dp[0] should be zero in that case.
Please upload some graph based questions
I'll see what I can do!
Kevin, thanks a million for the video. It exemplifies how to approach a question on the interview so that you can fit within the time constraints - something still eludes me.
It was a bit difficult to understand this it first and still found I had some gaps until I watched this video: czcams.com/video/5o-kdjv7FD0/video.html
For someone who has not done DP problems, it is a great visualization.
You did mention the stairs problem during your video and this is how I found the explanation I just posted above.
This is not to criticize your video but just to help everyone in the forum understand the general approach better.
What I got from both lessons is that Fibonacci is a simplified version of these more complex problems. Once you get that and the fact that you need to find a pattern for the base cases, the rest is easy :)
why dp[0]=1; ??
fib sequence with a condition
how do u do these questions soo quickly lol...
Harry Gong lots of practice!!!
I was asked this question by chase!
This guy jump to solution without discussing the approach.
function decodingWays(str){
let res = []
let obj = create() // a map of chars{1:'A'}...
let startChar = str.charAt(0)
if(obj[startChar]){
res.push(1)
}
for(let i =1; i
deserves more number of subscribers
haha thanks!!!
Video could have been more appealing if presenter can add some rationale to take 1-d dp array and what does it signify. It looked more like reading a leetcode solution. We don't want see solution, rather the rationale which isn't present in the video.
01 will return 0?
Correct
Because let twoDigits = Number(s.slice(i-2, i)) for "01" will be 1, which will skip (twoDigits >= 10 && twoDigits
It's also better to walk through an example.
How in da fuk can dp[0] not be 0 but dp[1] can be 0
Dp[0]= 0 ? there is no way
the current solution doesnt work for '27'. it may not work for
Input:
"10"
Output:
2
Expected:
1
Input:
"12"
Output:
1
Expected:
2
He didn't explain anything in this problem.
Asked by : Amazon and Paytm too**
I don't understand the logic "the number of ways to decode a string of length 0 is 1". How many ways can you decode an empty string? Zero. Why 1?
Very Easy top down solution with Memoization
public int numDecodings(String s) {
if (s.length() < 1)
return 0;
int[] memo = new int[s.length() + 1];
Arrays.fill(memo, Integer.MAX_VALUE);
return numDecodings(s, 0, memo);
}
private int numDecodings(String s, int index, int[] memo) {
if (index < s.length() && s.charAt(index) == '0') // check if it's zero
return 0;
if (index >= s.length() - 1)
return 1;
if (memo[index] != Integer.MAX_VALUE). // check if you already computer this value
return memo[index];
int total = numDecodings(s, index + 1, memo); // first case where you decode it as single
int value = Integer.parseInt(s.substring(index, index + 2));
boolean isDoubleDigit = (value > 9 && value < 27);
if (isDoubleDigit)
total += numDecodings(s, index + 2, memo); // second case where you decode it as double
memo[index] = total; // store the values in the memo for quick usage
return total;
}
You should explain the approach first. Simply jumping to solution looks like you have memorized the code.
Has anybody ever told you that you look so Indian?
Nice explanation bdw :p
Why always bottom up? I would love to see more top down approaches..Thanks!!
bad bad badcow
Not able to understand why we are doing dp[i] += dp[i-2]?? The way I understood the solution is that dp[0] is number of ways to decode input of length 0 and its value is 1. Same way dp[1] is number of ways to decode input of length 1 and its value is 1. So building on these base cases if we have 12 as input - we take either 1 or 2 and since its 1 digit we take value of dp[1] which is 1. moving on we consider both 12 which is a single entity but for this this why we are going back to dp[n-2] which is dp[0] which is number of ways to decode input of length 0? Please explain in layman terms if possible.