Decode Ways
Transitions
If
s[i] = '0'
, then invalid ways (0)If
s[i] = '1'
, then we can choose to takes[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 takes[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
Top-down
Modelling the transitions as-is gives us:
We can then memoize the value of each recursive call by index i
.
Bottom-up
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).
Last updated