Name: Facebookのコーディングインタビューの質問 - このメッセージを解読するにはどのように多くの方法がありますか？ (Facebook Coding Interview Question - How Many Ways to Decode This Message?)
Uploaded: 2021-01-14T10:24:40.000Z
Duration: 16 min 36 s
Description: VoiceTubeの動画で発音を聞きながら英語表現を覚えよう！学べる英語：

to 不定詞

Hey, everyone, today I have, according to be a question that's being asked by Facebook.

In this problem, you're given a mapping that's like this one.

法助動詞 A2

So in this, mapping the letter a maps to one, as you can see on B 22 and so on up to the which maps to 26 on with this mapping.

If we're given a message in the string, for example, a B, you can convert it to another string in this case, one, too, because a maps to one and be maps to two on.

In this problem, you're given the converted version of the string, for example, 12 Again, let's call it data for now on.

The problem is, can you write a function that takes this data as the input on returns?

The number of messages that could have been the orange, no message or, in other words, how many ways are there to decode this message back to the original message.

So, for example, if the given input is one too your function, let's call it numb ways off data should return to, because there are two possible messages that can be included into one too one of them is, as we saw earlier, A B and the other one is actually just no, because l maps to 12 on If you're given, for example, there one instead.

ETA Your function Numb ways of data should return there instead because there's no message that maps to their one.

Okay, try solving this problem in off and in time, where n is the number of letters and the given strength data and, by the way, just for simplicity.

You can assume that the given data string has on Lee did it inside, you know, between zero and nine.

If you want to try solving this problem by yourself on by the way this problem came from this website called Daily Quoting Problem, you can get more problems just like this one through my referral on discount link CS 20 dot io slash daily.

I would first think about simpler examples.

So, for example, what if you're given three asked the inputs, then there's only one message that can be encoded into three on.

So your function should return one on What if you're given the empty string, then there is no message.

Must have bean on empty String us well, so there's only one possible message here as well.

And what if you're given more complex inputs?

Well, in that case, let's examine the input.

Then we can think about the quoting it from left to right sequentially on at the beginning, there are two choices.

The 1st 1 is to look at the first letter one by itself.

And then they called it back to eight because, as we saw earlier, aye, maps to one on.

The second choice is to look at the first on the second letter together and then decoded back to El instead because l maps to 12.

Now, if you go with the first choice on decode one too, eh?

Then the whole message that you get by decoding the whole string will look like this.

You'll be a put together with whatever you get by decoding the rest of the message.

If you go with the second choice, Andi could 1 to 2 l What's gonna be left will be 345 So the whole message that you get by decoding the whole string will be l put together with whatever you get by decoding 345 the rest of the message.

So, actually, the number of ways we can decode this message 12345 will be the some off the number of ways we can decode 2345 on the number of ways we can decode 345 So that's what I wrote here.

Numb Ways of 12345 is the some off numb ways off.

2345 On Dumb Ways of 345 on This is starting to look like rickerson and ready.

Well, you might say Let's try the same thing.

One way to decode this is to look at the first letter and then decode it back.

The whole misses you get by decoding the whole string will be be combined with whatever you get by decoding the rest of the message.

And what if you look at the first on the second letters together?

Well, there's no single letter in our mapping system that maps directly to 27.

That's just because we only have up to the which maps to 26.

So actually, this is the only way to D could 2734 and five.

So the number of ways of decoding this message 2734 and five is equivalent to the number of ways of decoding 734 on five.

Let's take a look at just one more example here.

What if you're given a string that starts with zero at the beginning?

Well, in that case, there's no message that would and could into this string there 11 because no single letter maps to their or their one so numb ways off their 11 should return there.

Now, using all of these, let's write are functional, weaker, silly.

The 1st 1 is when the string is empty and the 2nd 1 is when the given string starts with a zero on for the recursive case, there are two cases.

The 1st 1 being when we need to call our function Recursive Lee twice on the 2nd 1 is when we need to only call the function because somebody wants Okay, let's see how we can turn this idea into code like we saw earlier.

We're gonna call our function Numb ways off.

Instead of calling this function recursive lee directly, we're gonna define another function.

We're gonna call this function and the cursory it's gonna take data.

The given string on K, which is going to be a non negative integer on in the helper function, were on Lee gonna look at the last K letters off data.

So, for example, if the given data is, let's say a B C D.

On if the Given K is three were on Lee gonna look at the last three letters B C D.

This way we don't have to create a new string.

Every time we call our function, we cursory on this helper function will return the number of ways we can decode the last K letters off the string.

And that means from our main function numb ways.

All we need to do is we just need to return hoper of data and there's length on dhe.

Okay, Now, in the helper function, let's take care of the two bass cases first.

The 1st 1 was when the string is empty, we need to return one.

So we're just gonna write if Kay or the number of letters we're going to look at is zero, then we're gonna return one.

And the second base case was when the first letter is zero.

We needed to return there to do this on to make it just a little bit more convenient.

We're gonna define a new viable called s, which is going to be the starting index off the letters that were examining That's there's length minus Kate.

We can say if Dana Scott Rockets s or the letter or the character at the index s off data is equal to zero, then we're gonna return.

So now the next case we need to take care of are the two recursive cases that we saw earlier the case where we need to call the recursive function twice on the case where we need to call the function recursive we only once.

But since we're not gonna call numb ways, we personally let's fix this new positions.

Okay, here we're calling the hoper function recursive Lee.

Instead, we're never gonna change the first arguments on in this first case right here we have 12345 Let's say K right now is five.

In that case, there are two ways to go about this.

The 1st 1 is to interpret the first letter by itself and then decode it back to A.

In that case, we're gonna call Helper with the same string on came on this one.

The second way is to interpret the 1st 2 letters together.

And then they called it back to El instead on For that, we're gonna call Helper with the same string again on K minus two.

So with the first week Ursula call came on, this one becomes four on.

We're going to look at these four letters and then with the second case, K minus two becomes three.

That's when, for example, we have 27345 asked the string on five as Kate.

In that case, there is no letter that maps to 27 so we only need to say we need to interpret to be and then take a look at the wrists off the string.

So we need to only call helper again with 27345 came out.

字幕リスト動画再生

Facebookのコーディングインタビューの質問 - このメッセージを解読するにはどのように多くの方法がありますか？ (Facebook Coding Interview Question - How Many Ways to Decode This Message?)

quote

strength

interpret

dumb