Digits Decoding

Posted: 10 Dec, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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
Approach 1
  • 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.
Try Problem