Digits Decoding

Posted: 10 Dec, 2020
Difficulty: Moderate

PROBLEM STATEMENT

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.

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.