New update is available. Click here to update.

Last Updated: 10 Dec, 2020

Difficulty: Moderate

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

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

```
Can you solve this using constant extra space?
```

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

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

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

```
1 <= T <= 10
1 <= N <= 10^5
0 <= SEQ[i] <= 9
Time limit: 1 sec
```

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

**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:

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

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.

Popular Interview Problems: