hey everyone today I have a coding
interview question that's being asked by
Facebook in this problem you're given a
mapping that's like this one so in this
mapping the letter A maps to one as you
can see and B to 2 and so on up to D
which maps to 26 and with this mapping
if you're given a message in a string
for example a B you can convert it to
another string in this case 1 2 because
a maps to 1 and B maps to 2 and in this
problem you're given the converted
version of the string for example 1 2
again let's call it data for now and the
problem is can you write a function that
takes this data as the input and returns
the number of messages that could have
been the original 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 1 2 your function let's call it
num ways of data should return 2 because
there are 2 possible messages that can
be encoded into one - one of them is as
we saw earlier a B and the other one is
actually just L because L maps to 12 and
if you're given for example 0 1 instead
as the data your function num ways of
data should return 0 instead because
there's no message that maps to 0 1 okay
try solving this problem in off n in
time where n is the number of letters in
the given string data and by the way
just for simplicity you can assume that
the given data string has only digits
inside you know between 0 and 9 ok pause
the video right here if you want to try
solving this problem by yourself and by
the way this problem came from this
website called daily coding problem you
can get more problems just like this one
through my referral and discount link si
esto Jota io / daily anyway here's my
solution
I would first think about simpler
examples so for example what if you're
given three as the input then there's
only one message that can be encoded
into three and that's simply the letter
C so your function should return one and
what if you're given the empty string
then the original message must have been
an empty string as well so there's only
one possible message here as well so
your function should return one okay and
what if you're given more complex inputs
for example this one one two three four
and five well in that case let's examine
the input one three four and five then
we can think about decoding it from left
to right sequentially and at the
beginning there are two choices the
first one is to look at the first letter
one by itself and then decode it back to
a because as we saw earlier a maps to
one and the second choice is to look at
the first and the second letter together
and then decode it back to L instead
because L maps to 12 now if you go with
the first choice and decode one to a
then the whole message that you get by
decoding the whole string will look like
this it'll be a put together with
whatever you get by decoding the rest of
the message two three four and five and
if you go with the second choice and
decode one to 2l what's gonna be left
will be three four five so the whole
message that you get by decoding the
whole string will be L put together with
whatever you get by decoding three four
five the rest of the message so actually
the number of ways we can decode this
message one two three four five will be
the sum of the number of ways we can
decode two three four five and the
number of ways we can decode three four
five so that's what I wrote here num
ways of one two three four five is the
sum of numbers of two three four five
and numb ways of three four five and
this is starting to look like recursion
anyway let's take a look at another
example what if you're given two seven
three four five instead well you might
say let's try the same thing so let's do
that one way to decode this is to look
at the first letter and then decode it
back to B and that way the whole message
you get by decoding the whole string
will be be combined with whatever you
get by decoding the rest of the message
seven three four and five and what if
you look at the first and the second
letters together well there's no single
letter in our mapping system that map's
directly to 27 and that's just because
we only have up to Z which maps to 26 so
actually this is the only way to decode
to seven three four and five so the
number of ways of decoding this message
to seven three four and five is
equivalent to the number of ways of
decoding seven three four and five and
that's what I wrote right here let's
take a look at just one more example
here what if you're given a string that
starts with 0 at the beginning well in
that case there's no message that would
encode into this string there are 1 1
because no single letter maps to 0 or 0
1 so num ways of 0 1 1 should return
there now using all of these let's write
our function recursively they're
basically two base cases here the first
one is when the string is empty and the
second one is when the given string
starts with at 0 and for the recursive
case there are two cases the first one
being when we need to call our function
recursively twice and the second one is
when we need to only call the function
recursively once ok let's see how we can
turn this idea into code like we saw
earlier we're going to call our function
num ways of data and instead of calling
this function recursively directly we're
going to define another function let's
call it just helper and we're gonna call
this function recursively
it's gonna take data the given string
and K which is going to be a
non-negative integer and in the helper
function we're only gonna look at the
last K letters of data so for example if
the given data is let's say ABCD and if
the given K is 3 we're only gonna look
at the last three letters BCD and this
way we don't have to create a new string
every time we call our function
recursively and this helper function
will return the number of ways we can
decode the last K letters of the string
and that means from our main function
num ways all we need to do is we just
need to return helper of data and Dara's
length and that's the full string okay
now in the helper function let's take
care of the two base cases first the
first one was when the string is empty
we need to return one so we're just
going to write if K or the number of
letters we're going to look at is 0 then
we're gonna return 1 and the second base
case was when the first letter is 0 we
needed to return 0 and to do this and to
make it just a little bit more
convenient we're gonna define a new
variable called s which is going to be
the starting index of the letters that
were examining that's there as length
minus K and using this we can say if
data square brackets S or the letter or
the character at the index S of data is
equal to 0 then we're gonna return 0 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 and the
case where we need to call the function
recursively only once this is the
notation we used earlier but since we're
not gonna call num ways recursively
let's fix this notation so we have
everything consistent okay here we're
calling the helper function recursively
instead we're never gonna change the
first argument
and in this first case right here we
have one two three four five now let's
say K right now is five in that case
there are two ways to go about this the
first one is to interpret the first
letter by itself and then decode it back
to a and in that case we're gonna call
helper with the same string and K minus
1 the second way is to interpret the
first two letters together and then they
code it back to L instead and for that
we're gonna call helper with the same
string again and K minus two so with the
first we curse we call K minus 1 becomes
four and we're gonna look at these four
letters and then with the second case K
minus two becomes three and we're gonna
take a look at the last three letters
let's also examine the second case
that's one for example we have two seven
three four five as the string and five
as K in that case there is no letter
that maps to 27 so we only need to say
we need to interpret two as B and then
take a look at the rest of the string
the last four characters so we need to
only call helper again with two seven
three four five and K minus 1 which is 4
so basically what we're gonna return
from helper of the string and K will be
either the sum of helper of the same
string and K minus 1 and helper of the
same string and K minus 2 or just helper
of the same string and K minus 1 I think
you'll notice that in either case we
have helper of the same string and K
minus 1 so let's store that in a new
variable called result by writing
results
EKOS helper of data k minus 1 and then
we need to add helper of the same string
k minus 1 to that result only when we
can interpret the first two letters of
the part of the string that we're
examining as a single letter so that's
when the first two letters the number
that it represents is less than or
go to 26 and also greater than or you go
to 10 we can check that by writing if K
is greater than or equal to 2 and int of
data square brackets s con s plus 2 is
less than or equal to 26 so we need to
first say K greater than or equal to 2
make sure that we have at least 2
letters in the part of the string that
we're examining and then let's just say
here that data square brackets
s : s plus 2 retrieves the substring
that we're interested in the first two
letters of the part of the string that
we're examining and then we need to
convert it to an integer and make sure
that that's less than or equal to 26 we
don't have to worry about that part
being greater than or equal to 10 here
actually because that part is already
taken care of when we check that data
square brackets S or the first letter of
the part of the string that we're
examining is not equal to 0 so if it
satisfies these two conditions
then we'll add helper of data comma K
minus 2 to the results and then after
that we just need to return results now
this solution works but it can be very
inefficient depending on the nature of
the input so let's see why that's the
case and for that let's examine the
worst case for this problem that's when
we're given a string that solely
consists of ones because then there are
many many ways to interpret this string
and if that was the case num ways of
let's say six ones that would go into
helper of the same string and six and to
find the value for that we need to find
the values for these two helper of the
same string and five and helper of that
string and four and here if we write
this one hopper of six ones and six as
age of six we'll see that to find the
value for H of six we need to first find
the values for H of 5 and H of 4 and to
find the return value for H of 5 we need
to first find the return values for H of
4 and H of 3 and so on and
just like we saw in my video about
Fibonacci sequence this is not the most
efficient approach because we need to
repeat some of the competition's over
and over again for example to find H of
4 here and here and this actually takes
about of 2 ^ and in time to find the
number of ways to interpret a string
with n letters inside and to fix this we
can just use dynamic programming and
memorization to do that let's say if
we're trying to find num ways of 1 1 1
then we'll create a new array with n
plus 1 elements or 4 elements in this
particular case and then we're going to
use this to store some of the
intermediate results from our function
we're gonna store helper of 1 1 1 K at
index K so if K is 1 that goes into this
one and this way helper of 1 1 1 and N
or the last value that we need to find
will go into the last index of this
array right here and with that our code
is going to look like this this is
almost identical to what we had earlier
except for these orange parts and the
first thing that's different
well is that we change the names a bit
you know we have none ways of DP and
helper of DP now and in num ways of DP
we first define a new integer array
whose length is the original data length
plus 1 so that's n plus 1 and then let's
say we want to initialize every element
of this array to now just like that and
then we're going to put it in a new
variable called memo and instead of
calling helper with data and data as
length which is what we did earlier
we're passing memo as an argument as
well now in helper DP after taking care
of the base cases if we have a value
already stored at index K of memo then
that's not gonna be now so if memo of K
is not now we're gonna return that value
instead of going through the whole
function and otherwise this is the first
time we're
running this function with this
particular K so we'll find the result
and then instead of returning results
right away we're gonna store it in memo
at index K and then we're gonna return
results okay and that's my solution and
with this solution it only actually
takes both n in time to find num ways of
the given string instead of two to the
power of n that we saw earlier and by
the way like I said earlier this problem
came from this website called daily
coding problem you can find a website
through my referral link CS dojo da io /
daily it's a website that gives you a
daily coding problem to practice with
and it's actually a website that's run
by a friend of mine I used to work with
at Google if you use my referral link
it's gonna give you a 10% discount on
their premium subscription but I would
say even their free option and their
blog articles that you're looking at
right now are pretty good anyway thank
you so much for watching my videos as
always and I'll see you guys in the next
video