Decoding Ways

You are given an encoded message containing digits. Each digit or pair of digits can be mapped to a letter using the mapping:

\( 'A' \leftrightarrow 1, 'B' \leftrightarrow 2, \ldots, 'Z' \leftrightarrow 26 \).

Your task is to determine the number of ways to decode the message. A valid decoding cannot contain any leading zeros in any valid group of digits.

For example:
Input: "12"
There are two decodings: "AB" (1 2) and "L" (12).

The solution uses a dynamic programming approach where we define a dp array such that:

\( dp[i] = \begin{cases} dp[i-1] & \text{if the single digit } s[i-1] \text{ is valid (i.e. } 1 \leq s[i-1] \leq 9)\ \end{cases} \)

and

\( dp[i] += dp[i-2] \quad \text{if the two-digit number } s[i-2:i] \text{ is between } 10 \text{ and } 26. \)

inputFormat

The input consists of a single line containing a non-empty string of digits representing the encoded message.

outputFormat

Output a single integer representing the total number of possible decodings of the input message.

12

2