Digits Decoding

Let’s understand the problem in the previous approach by an example 

Suppose we have a sequence 1111, So, now, let’s plot the recursive tree for the above recursive solution.

As we can see in the above diagram:

• { seq, 0 } is calculated 4 times
• { seq, 1 } is calculated 3 times
• { seq, 2 } is calculated 2 times
• { seq, 3 } is calculated 1 time
• { seq, 4 } is calculated 1 time

Note: Subproblem { seq, n } means a problem with ‘seq’ as digit sequence and ‘n’ as the size of the sequence.

To optimize the overlapping sub-problem calculation, we will use memoization by storing answers for each recursive state.

Approach: 

• The idea is to use memoization.
• Create a lookUp array of size N+1 to store the answers to the subproblems where lookUp[i] denotes the possible number of ways to decode the subsequence of length i. Here, the subsequence is from index 0 to index i-1.
• Initialize the lookUp array with -1 which denotes that it is not calculated yet.
• We will call a helper function that returns us the number of valid decodings.
• The algorithm for the helper function will be as follows: 
  
  Int helper(seq, n):
• If n <= 1, means only 1 way of encoding it is possible:
      Return 1.
• If lookUp[n] != -1, means we have already calculated the answer for this sub-problem,
      Return lookUp[n]
• Initialize ans = 0
• If the last digit is not 0:
      Call ans += helper(seq, n-1)
• If the last 2 digit number lies in 10 to 26:
      Call ans += helper(seq, n-2)
• Assign lookUp[i] = ans, to store it for further use.
• Return lookUp[i].

• The idea is to create a DP array of size N+1.
• Initially, all the elements of the DP array will be 0.
   
• Now, the value DP[i] is the number of decodings possible for a  subsequence of length i. Thus, initialize DP[0] and DP[1] as 1. 
  Example: DP[1] for string “123” contains the number of decodings for subsequence “1”. 
  Similarly, DP[2] contains a number of decodings for subsequence “12”.
   
• Let us understand it by an example of string “123”
  Firstly DP[0] and DP[1] are made 1, for DP[1], the possible string is {A}. 
  Now, for DP[2], we will consider the subsequence ‘12’ and the character ‘2’:
   
• When we add B in place of 2, the number of decodings for ‘12’ remains the same as the number of decodings for ‘1’ i.e. {AB}. Thus, DP[2] = DP[1].
   
• There is 1 more decoding possible if we consider ‘12’ as L, thus, we make DP[2] equal to the sum of DP[2] ({AB}) and DP[0]. The decodings will be {‘AB’, ‘L’}. This makes DP[2] = DP[2] + DP[0] = 2 if and only if the integer generated from the last 2 characters is less than 27.
• Now, for DP[3], 
  
  • First, DP[3] = DP[2]
  • Second, as 23 is less than 27, DP[3] = DP[3] + DP[1].
  • The possible decodings are {‘ABC’, ‘LC’, ‘AW’’} 
    
    Summary: 
    For “123”
    DP[0] = ‘ ’
    DP[1] = ‘A’ which is ‘ ’ + seq[0].
    DP[2] = ‘AB’, ‘L’ which is [ ‘A’ + seq[1], ‘ ’ + seq[01]]
    Similarly, DP[3] = ‘ABC’, ‘LC’, ‘AW’
     
• The detailed algorithm to fill the DP array will be as follows:
  Loop : For i = 1 to N-1:

1. If seq[i] != 0:
       DP[i+1] = DP[i]
2. If seq[i-1] * 10 + seq[i] lies in 10 to 26:
       DP[i+1] += DP[i-1]
3. DP[i+1] %= 1000000007

• Return DP[N]. 
• Let us understand the above algorithm with the example seq = 132
  Initially DP array will be { 1, 0, 0, 0 }
  Now let’s track the DP array for each iteration

1. For i = 0
   The first condition is true. So, DP[1] = DP[0]
   The second condition is false.
   Thus, DP = { 1, 1, 0, 0 }
    
2. For i = 1
   The first condition is true. So DP[2] = DP[1]
   The second condition is also true. So, DP[2] += DP[0]
   Thus, DP = { 1, 1, 2, 0 }
    
3. For i = 3
   The first condition is true. So, DP[3] = DP[2]
   The second condition is false.
   Thus, DP = { 1, 1, 2, 2 }
   
   Thus, the answer will be DP[3], which is 2.

We may realise from the previous approaches that we only need the last 2 values of the DP array to fetch the current answer.

In this approach, we will be working on this idea. 

• The idea is to store answers for the last 2 iterations in 2 variables named prev1 and prev2.
• Initially, prev1 = 1 denoting answer for a sequence of size 1 and prev2 = 1 denoting answer for a sequence of size 0.
• The detailed algorithm to calculate new answer is as follows:
  Loop : For i = 1 to N-1:
• Initialize cur = 0
• If seq[i] != 0:

1. cur += prev1

• If (seq[i-1] * 10 + seq[i]) lies in 10 to 26:

1. cur += prev2

• cur %= 1000000007
• Assign prev2 = prev1
• Assign prev1 = cur
  
  Finally, Return prev1.