Digits Decoding
A few days back, Ninja encountered a string containing characters from ‘A’ to ‘Z’ which indicated a secret message. For security purposes he encoded each character of the string to its numeric value, that is, A = 1, B = 2, C = 3, till Z = 26 and combined them as a single sequence (SEQ) of digits of length N. Let's say the message was "LA", Ninja encoded it as 121 for L=12 and A=1.

Today, when he read the encoded secret message, he realised that he was not able to decode the original string. So, the Ninja is wondering in how many ways he can decode the numeric sequence to some valid string.

A valid string is a string with characters from A to Z and no other characters.

Example:

Let the encoded sequence be 121, The first way to decode 121 is: 1 = A 2 = B 1 = A Thus, the decoded string will be ABA. The second way to decode 121 is: 12 = L 1 = A Thus, the decoded string will be LA. The third way to decode 121 is: 1 = A 21 = U Thus, the decoded string will be AU. So, there will be 3 ways to decode the sequence 121 i.e. [(ABA), (LA), (AU)].

Note:

The input sequence will always have at least 1 possible way to decode. As the answer can be large, return your answer modulo 10^9 + 7.

Follow Up:

Can you solve this using constant extra space?

Input format:

The first line of input contains an integer T denoting the number of queries or test cases. The first and only line of each test case contains a digit sequence.

Output format:

For each test case, print the number of ways to decode the given digit sequence in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Digits Decoding

A few days back, Ninja encountered a string containing characters from ‘A’ to ‘Z’ which indicated a secret message. For security purposes he encoded each character of the string to its numeric value, that is, A = 1, B = 2, C = 3, till Z = 26 and combined them as a single sequence (SEQ) of digits of length N. Let's say the message was "LA", Ninja encoded it as 121 for L=12 and A=1.

Today, when he read the encoded secret message, he realised that he was not able to decode the original string. So, the Ninja is wondering in how many ways he can decode the numeric sequence to some valid string.

A valid string is a string with characters from A to Z and no other characters.

Example:

Let the encoded sequence be 121,

The first way to decode 121 is:
1 = A
2 = B
1 = A
Thus, the decoded string will be ABA.

The second way to decode 121 is:
12 = L
1 = A
Thus, the decoded string will be LA.

The third way to decode 121 is:
1 = A
21 = U
Thus, the decoded string will be AU.

So, there will be 3 ways to decode the sequence 121 i.e. [(ABA), (LA), (AU)].

Note:

The input sequence will always have at least 1 possible way to decode.    

As the answer can be large, return your answer modulo 10^9  + 7.

Follow Up:

Can you solve this using constant extra space?

Input format:

The first line of input contains an integer T denoting the number of queries or test cases. 

The first and only line of each test case contains a digit sequence.

Output format:

For each test case, print the number of ways to decode the given digit sequence in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10   
1 <= N <= 10^5
0 <= SEQ[i] <= 9

Time limit: 1 sec

Accepted Answer

Simply try building a recursive solution first and then change it to iterative one.
This problem is recursive and can be broken into sub-problems. We start from the end of the given digit sequence. We initialize the total count of decodings as 0. We recur for two subproblems.
1) If the last digit is non-zero, recur for remaining (n-1) digits and add the result to the total count.
2) If the last two digits form a valid character (or smaller than 27), recur for remaining (n-2) digits and add the result to the total count.

Accepted Answer

Recursion

The idea is to use recursion to reduce the big problem into several small subproblems.
We will call a helper function that returns us the number of valid de-codings.
The helper function works in a way that initially, we will pass the sequence of length n to it.
Further, we will calculate the possible answer for the subsequence of length n-1 recursively.
Similarly, if it's valid, we will calculate the possible answer for the subsequence of length n-2 recursively.
Will work upon these two calls to get the final answer.
The algorithm for the helper function will be as follows:

Int helper(seq, n):
If n <= 1, means there is only 1 way to decode it,
Return 1.
Initialize ans = 0
If the last digit is not 0:
Call, ans += helper(seq, n-1)
If the integer generated by the last 2 digits lie between 10 to 26:
Call ans += helper(seq, n-2)
Return ans.

Space Complexity: O(n)Explanation:

O(N) per test case where N is the size of the sequence.

In the worst case, extra space will be used by the recursion stack as there can be a maximum of N number of recursive calls at a time.

Time Complexity: OtherExplanation:

O(1.61 ^ N) per test case where N is the size of sequence and 1.61 is the Golden Ratio or Fibonacci Ratio.

In the worst case, there will be a Fibonacci(n) number of possible decodings. Thus, We are making 1.61 ^ N calls for the sequence.

Accepted Answer

Recursive Memoization

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].

Space Complexity: O(n)Explanation:

O(N) per test case where N is the size of the sequence.

In the worst case, we are using a memoization array of size N.

Time Complexity: O(n)Explanation:

O(N) per test case where N is the size of the sequence.

In the worst case, the maximum of 3 calls are made for all sizes of sequences and there are N possible sizes for a sequence. Thus, O(3*N).

Accepted Answer

DP Bottum Up

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:

If seq[i] != 0:
DP[i+1] = DP[i]
If seq[i-1] * 10 + seq[i] lies in 10 to 26:
DP[i+1] += DP[i-1]
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

For i = 0
The first condition is true. So, DP[1] = DP[0]
The second condition is false.
Thus, DP = { 1, 1, 0, 0 }
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 }
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.

Space Complexity: O(n)Explanation:

O(N) per test case where N is the size of the sequence.

In the worst case, we are using a DP array of size N.

Time Complexity: O(n)Explanation:

O(N) per test case where N is the size of the sequence.

In the worst case, the loop performs its tasks in constant time for N times.

Accepted Answer

Space optimized DP

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:

cur += prev1

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

cur += prev2

cur %= 1000000007
Assign prev2 = prev1
Assign prev1 = cur

Finally, Return prev1.

Space Complexity: O(1)Explanation:

O(1) per test case,

In the worst case only constant extra space is used.

Time Complexity: O(n)Explanation:

O(N) per test case where N is the size of the sequence.

In the worst case, the loop performs its tasks in constant time for N times.

Today, when he read the encoded secret message, he realised that he was not able to decode the original string. So, the Ninja is wondering in how many ways he can decode the numeric sequence to some valid string.

A valid string is a string with characters from A to Z and no other characters.

Example:

Note:

Follow Up:

Input format:

Output format:

Note:

Constraints:

Top Daffodil Software Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Daffodil Software Software Developer