We know there are three steps to a DP problem.
- Storage and Meaning:
We will store the results in an array, let's say dp. Now dp[i] will store the number of encodings possible till the i-th char. This is our meaning.
Clearly, if we are at the 0-th char the number of encodings is 1. [Unless we have an invalid string], So this problem is easier compared to calculating the number of encodings till the n-th char. So we found out the direction which is from left to right.
- Travel and Solve:
Now to solve this we will need to find our recursive relation. Let's say we are at the i-th char then we can either consider the i-th char independently or attach the i-th char with the previous value. But in both cases, we need to check the validity. So, in a way, it becomes a slight variation of the Fibonacci problem.
Let's take this example arr: [2, 3, 1, 0, 1, 1]
First, let's solve the trivial case.
We can create an encoding of "b" using 2. So dp=1
Now, for 3 we have two options:
- Attach 3 to the previous 2 which gives us 23 i.e "w".
- Keep 3 separate which gives us "bc".
Now for 1 we can just attach "a" to the previous encodings, giving us "bca" and "wa". But we can try one more thing: attach 1 to 3 and keep 2 separate. So it will be 2-31. But there is no valid encoding for 31. Hence we cannot consider this. So here dp = 2
Now that we have 0, we cannot consider 0 independently i.e 231-0 will not be valid. Rather we should consider 23-10. Where 23 gives up 2 encodings and 10 stands for "j".
Now that we have 1 we can consider it separately and simply attach "a" to all the encodings before it. i.e 2310-1.
Now there is another split i.e 231-01 but 01 is an invalid split. So we won't consider it.
Now for the final element 1, we can make two splits. Like 23101-1 and 2310-11.
In the first split, we can simply append "a" to the previous encodings.
In the second split, we have to append "k" to the 2nd previous encodings, Hence we have 4 encodings in total.
Clearly, for every i we are looking at two things i-1 and i-2. Let's look at the various combinations of i and i-1
i = 0 and i-1 = 0
Here we cannot keep i separate nor can we take i and i-1 together. So it is an invalid scenario.
i = non-zero and i-1 = 0
In this case, we can only treat i separately. We cannot treat i-1 and i together because they will form numbers like 03, 04 which are invalid.
So one case here.
i = 0 and i-1 = non-zero
Here we cannot keep i separate rather can add i and i-1 together. So there is also just one case here.
i = non-zero and i-1 = non-zero
Here we can keep i separate. We can also keep i and i-1 together but on the condition that the number they form should be less than 27.
Now we can move onto the code. Try to code it yourself if you are stuck then you should check out the solution.