# Digits Decoding

Posted: 10 Dec, 2020

Difficulty: Moderate

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

Approach 2

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

Approach 3

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

Approach 4

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.