## 639. Decode Ways II

A message containing letters from `A-Z` is being encoded to numbers using the following mapping way:

```'A' -> 1
'B' -> 2
...
'Z' -> 26
```

Beyond that, now the encoded string can also contain the character '*', which can be treated as one of the numbers from 1 to 9.

Given the encoded message containing digits and the character '*', return the total number of ways to decode it.

Also, since the answer may be very large, you should return the output mod 109 + 7.

Example 1:

```Input: "*"
Output: 9
Explanation: The encoded message can be decoded to the string: "A", "B", "C", "D", "E", "F", "G", "H", "I".
```

Example 2:

```Input: "1*"
Output: 9 + 9 = 18
```

Note:

1. The length of the input string will fit in range [1, 105].
2. The input string will only contain the character '*' and digits '0' - '9'.

b'
\n\n

## Solution

\n
\n

#### Approach #1 Using Recursion with memoization [Stack Overflow]

\n

Algorithm

\n

In order to find the solution to the given problem, we need to consider every case possible(for the arrangement of the input digits/characters)\n and what value needs to be considered for each case. Let\'s look at each of the possibilites one by one.

\n

Firstly, let\'s assume, we have a function `ways(s,i)` which returns the number of ways to decode the input string , if only the characters upto the \n index in this string are considered. We start off by calling the function `ways(s, s.length()-1)` i.e. by considering the full length of this string .

\n

We started by using the last index of the string . Suppose, currently, we called the function as `ways(s,i)`. Let\'s look at how we proceed. At every step, we need \nto look at the current character at the last index () and we need to determine the number of ways of decoding that using this character could \nadd to the total value. There are the following possiblities for the character.

\n

The character could be a `*`. In this case, firstly, we can see that this `*` could be decoded into any of the digits from `1-9`. Thus, for every decoding possible \nupto the index , this `*` could be replaced by any of these digits(`1-9`). Thus, the total number of decodings is 9 times the number of decodings possible \nfor the same string upto the index . Thus, this `*` initially adds a factor of `9*ways(s,i-1)` to the total value.

\n \n

Apart from this, this `*` at the index could also contribute further to the total number of ways depending upon the character/digit at its preceding\n index. If the preceding character happens to be a `1`, by combining this `1` with the current `*`, we could obtain any of the digits from `11-19` which could be decoded\n into any of the characters from `K-S`. We need to note that these decodings are in addition to the ones already obtained above by considering only a single current \n `*`(`1-9` decoding to `A-J`). Thus, this `1*` pair could be replaced by any of the numbers from `11-19` irrespective of the decodings done for the previous \n indices(before ). Thus, this `1*` pair leads to 8 times the number of decodings possible with the string upto the index . Thus, this adds\n a factor of `9 * ways(s, i - 2)` to the total number of decodings.

\n

Similarly, a `2*` pair obtained by a `2` at the index could be considered of the numbers from `21-26`(decoding into `U-Z`), adding a total of 6 times the \n number of decodings possible upto the index .

\n \n

On the same basis, if the character at the index happens to be another `*`, this `**` pairing could be considered as \n any of the numbers from `11-19`(9) and `21-26`(6). Thus, the total number of decodings will be 15(9+6) times the number of decodings possible upto the index .

\n

Now, if the character could be a digit from `1-9` as well. In this case, the number of decodings that considering this single digit can \n contribute to the total number is equal to the number of decodings that can be contributed by the digits upto the index . But, if the character is
\n a `0`, this `0` alone can\'t contribute anything to the total number of decodings(but it can only contribute if the digit preceding it is a `1` or `2`. We\'ll consider this case below).

\n

Apart from the value obtained(just above) for the digit at the index being anyone from `0-9`, this digit could also pair with the digit at the \n preceding index, contributing a value dependent on the previous digit. If the previous digit happens to be a `1`, this `1` can combine with any of the current \ndigits forming a valid number in the range `10-19`. Thus, in this case, we can consider a pair formed by the current and the preceding digit, and, the number of \ndecodings possible by considering the decoded character to be a one formed using this pair, is equal to the total number of decodings possible by using the digits \nupto the index only.

\n

But, if the previous digit is a `2`, a valid number for decoding could only be a one from the range `20-26`. Thus, if the current digit is lesser than 7, again\nthis pairing could add decodings with count equal to the ones possible by using the digits upto the index only.

\n

Further, if the previous digit happens to be a `*`, the additional number of decodings depend on the current digit again i.e. If the current digit is greater than \n`6`, this `*` could lead to pairings only in the range `17-19`(`*` can\'t be replaced by `2` leading to `27-29`). Thus, additional decodings with count equal to the\ndecodings possible upto the index .

\n

On the other hand, if the current digit is lesser than 7, this `*` could be replaced by either a `1` or a `2` leading to the \ndecodings `10-16` and `20-26` respectively. Thus, the total number of decodings possible by considering this pair is equal to twice the number of decodings possible upto the \nindex (since `*` can now be replaced by two values).

\n

This way, by considering every possible case, we can obtain the required number of decodings by making use of the recursive function `ways` as and where necessary.

\n

By making use of memoization, we can reduce the time complexity owing to duplicate function calls.

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . Size of recursion tree can go upto , since array is filled exactly once. Here, refers to the length of the input \nstring.

\n
• \n
• \n

Space complexity : . The depth of recursion tree can go upto .

\n
• \n
\n
\n

#### Approach #2 Dynamic Programming [Accepted]

\n

Algorithm

\n

From the solutions discussed above, we can observe that the number of decodings possible upto any index, , is dependent only on the characters upto the \nindex and not on any of the characters following it. This leads us to the idea that this problem can be solved by making use of Dynamic Programming.

\n

We can also easily observe from the recursive solution that, the number of decodings possible upto the index can be determined easily if we know \nthe number of decodings possible upto the index and . Thus, we fill in the array in a forward manner. is used to store the \nnumber of decodings possible by considering the characters in the given string upto the index only(including it).

\n

The equations for filling this at any step again depend on the current character and the just preceding character. These equations are similar \nto the ones used in the recursive solution.

\n

The following animation illustrates the process of filling the for a simple example.

\n

!?!../Documents/639_Decode_Ways_II.json:1000,563!?!

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . array of size is filled once only. Here, refers to the length of the input string.

\n
• \n
• \n

Space complexity : . array of size is used.

\n
• \n
\n
\n

#### Approach #3 Constant Space Dynamic Programming [Accepted]:

\n

Algorithm

\n

In the last approach, we can observe that only the last two values and are used to fill the entry at . We can save some \nspace in the last approach, if instead of maintaining a whole array of length , we keep a track of only the required last two values. The rest of the \nprocess remains the same as in the last approach.

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . Single loop upto is required to find the required result. Here, refers to the length of the input string .

\n
• \n
• \n

Space complexity : . Constant space is used.

\n
• \n
\n
\n

Analysis written by: @vinod23

\n
'