What's up guys, my name is Michael and welcome to my YouTube channel. Today we're going to go over a problem called alpha code, which is on spodge. Basically, you are given, uh, Alice is saying that, uh, you're given this code, a simple code and basically you're just translating, assigning eight, uh, to the word one, to the number one, B to the number two, three, uh, C to the number three, E to D to number four, so on, so forth until a Z is the number 26.  Cause if you're given the number, let's say two, five, one, one, four, and you're, you translated backwards, you can actually get many different letters such as a bean, you could get B, YAD, YAN, YKD, B, KD, and so on, so forth. So now what they, they're asking you is that how many different encodings can you get if you're translating backwards from the number back to the letter? Okay, so that's, that's basically the problem statement. How many different encodings if you're translating backwards from the number to the letter? So, um, if you look at this number, two, five, one, one, four, the reason why you could get many different translations is that if we look at here, two, five, one, one, four, whoops, uh, yeah, two, five, one, one, four. So if you look at this, you could actually, and we look at our translation encoding, A is one, B is two, and Z is up to 26, right? Um, we, one, we could translate it, this, uh, this encoding by each individual digit, so we could say like two is equal to B, so we would translate this to B, five is equal to E, so we translate this to E, one is A, so we translate this to A, and this to A, and then four is D, so we translate this to D. So you could get B, but another way you could translate this is actually to take this number, two, five, you actually could do it like this, right? Each individual, every two digits. So if you do it this way, you could actually realize that you have two, five, which is 25, and that's, you could change 25 into Y, so this would be Y, 11 could be changed into K, so this would be K, and then four could be changed into D, which is the same thing. But this is not the only way you could interpret this as, you can interpret this as 25, 114, right? You could interpret this as 14, 25, and then a one. So then this would actually translate to Y, A, and then 14, which is N, N, right? So there's so many different ways you can interpret this, this letter, this number encoding and translating it into letters. So our job is just to figure out how many different encodings you could have, right, for like B, Y, N, Y, N. Okay. So yeah, that's basically the the basically just the problem. Okay, so now I'm going to explain how to do the solution. Okay, guys, so what you realize in this problem is that let's say I'm given a letter A. Let's say I'm gonna give in a letter A, and then yeah, if I'm given a letter A, I could just convert this letter A into its equivalent number form, right? But let's say I have B. So what could what happens now? How can I interpret this when I have AB? If you have AB, you can interpret this in two different ways, right? So the first two ways, the first way is to interpret as separate. So A, and then a separate and then a B. This is just a delimitation and separate. And then you could translate this into like A, which is one, and then to B, two. And then this would be a translation, right? 12. Another thing you could do is that you could actually concatenate AB as a concatenation. So a value that you actually added. So like a B is actually equal to a times 10 plus B, right? Because if if each of these A and B are digits, right? We're saying them, they both are digits. So you could actually represent this a times 10 plus B. And given this state, given this state, if this state is between our corresponding coding between one and 26, then we could actually add, we should actually keep track of the count and include this as the different number of numbers to include, right? So that's basically the gist of the problem. You need to have two states. We need dynamic programming two states. One is to interpret this as a regular individual numbers. The second state is to actually interpret that interpret this when you multiply them together and add them. So yeah, that's the two different states. And then I'm going to explain like scenario how you would do it. Alright, guys, so this is the third time me trying to explain this because I failed at explaining it so many times. This is my third take anyway. So in order to try to solve this problem, remember the two states that I talked about about thinking of them separately and thinking them together. So what we're going to do is we are actually going to keep a array called count. And this array is going to keep track for every ith position in our string of 123. What it's going to do is that it's going to keep track the number of different different ways you could translate it for every ith position, right? So let's look at the first digit one. So the digit one. How many ways can you actually translate it? Well, if the digit is between one to nine, right, then that means we could translate it back to its equivalent letter form, right? 12345679, you could translate that if it's greater than nine, like JK, well, first of all, that's not even possible. Because if it's greater than nine, yeah, it's not, you can't have two digits for one digit, right? That's not possible. So it only could be one in nine. And if it's these, then you could translate it at most once, right? Because whichever digit you have 123456789, you only could translate it to its corresponding letter. So A, B, C, D, E, F, G, H, I. So that that count of number of different ones you could have is only one. Okay, so now let's look at two. Okay, so now let's look at two. So at one two, the remember the ith position is how many different digits at the ith position. So one two, we're actually keeping track of one two like this, right? One two, like this. And in one two like this, let's keep track of the two states that we talked about before. So the first state that we talked about is that assuming that we're just translating them individually. So if we have one two like this, individual translations, right? So we're going to, if I change one two, I'm going to translate it to its equivalent digit, we have one, you can make it into a, and then two can make it into b. So how many different, different, different letters can you actually have different combinations of the yeah, well, compare this to the original one of a, just concatenating two onto it doesn't actually change any of its, the number of different ways you could have it, right? Because if you look at this, this only could translate to A, B, if you think about it individually. So a translating this to AB is only one, there's only one way of AB, there's only one, one translation. So that's still going to equal to one. And comparing that with a, that's the same thing as one. Right? So it doesn't change. If we're thinking about individually, if I concatenate another digit, there's a number of different translations doesn't change. So for this case, for just thinking about individually, it's just going to equal to the same number of ways of the previous one. So what is the previous one? I minus one. So normally, when we're looping through all the digits, the count of the count of I is going to equal to I minus one count of I minus one. Okay, so that's what it means. So the count of the previous one is still going to be one, so it's going to equal to one. So now, now, we can't just think about it individually concatenating it, right? We also have to think about it when it's together of one two. So now it's 12. Right? So now we're thinking about a 12. Well, can we actually translate this 12 into its corresponding letter? Yes, you can. Right? So now let's think if we can translate it into it, how many different ways can you do it? Well, you have to add by the number of different ways of concatenating it to its two letters before it. And what I mean by that is that the number of different ways of 12 is actually of having 12 is actually the same thing as the number of different ways of an empty string concatenated with 12. Right? So the different ways of empty string is actually still going to be the same as one of count of one. So this is going to equal to one, right? So number of different ways of 12 is going to equal to the empty string number of different ways of empty string plus equal to 12 or whatever translation of 12 equals to right. So our current number of different ways of 12 is actually one. We see here one. So we're actually going to add the different ways of empty string plus equal to one. So this is going to be one plus one. So this is going to be two. Okay. Now, now we're going to get to one 222. And I'm actually going to clear most of these strings in order to in order to make it better because we don't need it anymore. Okay, so now we're at one 222. I think it was three originally. Yeah. So now we have count. It was one two. So now we are thinking about one 222. So like I said before, if you're just going to consider concatenating another digit, it's still going to be the same as the previous digit, right? No matter how many digits you add, it's still going to be the original count is going to be the same as before. So it's going to be how many different ways can you have of 12? It's going to be the same thing as how many different ways of 12. So this is going to be two. Okay. So now let's think about this. Now we have to think about it. Think about it, concatenating the right most digit, the previous digit with what you're currently digit you have, right? Because we have to consider this case also. If I could catnate just the previous digit and my current digit, because that's that's what you have to consider that also, right? So in this case, we have 22 22 and 22 you actually can look it up. So 22 can look up equals the V. So because of this, we're going to actually concatenate it with how many different ways of one of one. So like we have one 222, right? We're thinking about 22 and one. So we're going to actually add how many ways of 22 plus equal to the number of ways of one to get one 222. So number of ways of one is it is still is one, right? Our count of one. And 22 is two. So we're going to add these two up. One plus two is going to get to three. So this is going to give us three. Okay. So now let's look at the fourth one. So one plus two is going to give us three. And yeah, three. So now let's look at the fourth way here. 123. So how many different ways can you actually do this? It's just going to be the same as the previous one because concatenating a new digit doesn't actually change anything originally. So it's going to be three. But then now we have to think about having this case of 23 and one two. So when it's 2312 and then 23. Yeah, 23 does 23 work. So 23 does actually, you can actually look up 23. So it's W. So then this is actually, we're going to add whatever how many ways we could do at 23 plus equal to the ones that we have of 12 here of one two 12. And that's two. So we're going to actually add three plus two. Here in this case, there's three. Here this one is two. So we're going to add them together. Three plus two is going to give us five. So we're going to change this to five. So five is actually the answer of how many different ways you could have 123. And that's basically the solution of how the solution works. All right, guys, now I'm going to explain the code and then I'll be on my way. So first, we're going to read in our string n. They said to keep reading it until n is zero. So what I did was I did a while loop, it's not equal to zero. And at the end of the condition, I'm going to read in n our string. Okay, so here I created a length, size of length, so I don't have to keep calling n dot size. So that's just the length of the restraint. So what I did here is I created an array called DP because we're using dynamic programming. That's basically our count array. But that's basically what I did here. So we have DP is the dynamic programming of it. So the first state, remember, if it's just one digit, we're going to have it equal to one, because that's just one digit. Then I loop from one to the length of the string. I'm going to convert this string into its equivalent digit form. So for each character, for each character, I'm going to convert it to its equivalent digit form. So if it's like 123 or 579, I'm going to convert it, right? If it's greater than zero, then I'm going to set the current, the number at the current position that I'm currently at is going equal to the previous one. Because that's how normal works, right? That's how we explain. Okay. Now this is when the stuff gets more interesting. So remember, I have to check the value of each digit when it's separate and concatenated with the previous digit. So remember, we had like one, two, three. After if I'm at this last position, I have to check two, three to see if that works. So that is actually equal to the previous digit multiplied by 10 plus the current digit of three. So you have previous digit two times 10 is 20 plus three is 23. So that's where I had to do that here, right? So this number is vowel is going to be the previous digit converted, the character converted to its number format and the multiple by 10. And I'm going to add by the current digit converted to number format. Now here, I have to check if my current value is greater than or equal to 10 and less than or equal to 26. Because that's the, that's the how many, that's the way of two digits, right? For it's greater than or equal to 10 is this side, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, and Z, right? Because that's checking if the two digits concatenated together, you could actually look it up. So like 23. If you could look it up, stuff like that. Yeah, if it's two digits, you can actually concatenate together to look it up. So if that's the case, then I'm going to add by the count of the previous digit, i minus two. Okay. If the current value is less than, if the current value of i is less than two, then I'm just going to add by zero, right? Which is that just one, right? This is because like if, if I'm, I don't, I don't want to get like out of bounds, I want to keep track of my count. So if it's like, if I'm at this position, right, of zero one, I would need to add it by negative two, one minus two is negative one, right? The count of negative one. But that gives out of bounds. And we know that anything before this position is going to add by one, which is our count of one. So that's what we had to do that there. So yeah, no matter what, if the pre, the position is like less than two, then you're just going to add by one. Yeah, dp is zero is just one. So yeah, in that case for that. Yeah, so that's basically a code. At the end, I'm going to print out the dp of the count array of last value at length minus one, which is the last value. And yeah, then I read in my position event. So yeah, that's basically how you do this problem. You guys understand this problem. Rate, com, subscribe. I'll check you guys later. Peace.