Decode Ways
Last updated
Last updated
If s[i] = '0'
, then invalid ways (0)
If s[i] = '1'
, then we can choose to take s[i]
as it is, or pair it with the next digit (no matter what, it will form a valid number)
If s[i] = '2'
, then we can choose to take s[i]
as it is, or pair it with the next digit as long as the next digit is from '0'
to '6'
Any other digits have to be taken as it is
Modelling the transitions as-is gives us:
We can then memoize the value of each recursive call by index i
.
To solve this problem using bottom-up, let's re-frame the problem. However, notice that we cannot use the prefix of the array. This is because if we were to use the prefix s[:i+1]
, we would need to look-ahead to s[i+1]
, which should not be available yet. So we can re-framing the problem using suffixes instead:
Looking at the example above, if we have index i
, then we can use the values computed from i+1
onwards to figure out how many ways there are to form s[i:].
This gives us the recurrence relation:
Notice that it looks very similar to the original recurrence as we are essentially doing the same operations.
Note that the default values of s1
and s2
are both derived from the two base cases we have, with s1 = 1
because i = |s|
and s2 = 0
because i > |s|
(out of bounds so no ways to form it).
Given , can we find out how many ways there are to form ?
Trick: Implementing recurrence relations If the recurrence relation looks like , then it must be processed from left to right using prefixes. If it looks like , then it must be processed from right to left using suffixes.
We can also apply the state caching optimization, where .