Secret Message Decoding Problem

Ninja encountered an encoded secret message where each character from 'A' to 'Z' is mapped to a numeric value (A = 1, B = 2, ..., Z = 26). Given a numeric sequence (SEQ) derived from such encoding, determine how many ways the sequence can be decoded back into a valid string.

Input:

The first line contains an integer T representing the number of test cases. Each test case consists of a single line with a digit sequence.

Output:

For each test case, output the number of ways to decode the provided digit sequence in a separate line.

Example:

Input:

1 121

Output:

3

Explanation:

Three possible decodings for sequence '121' are 'ABA', 'LA', and 'AU'.

Constraints:

1

Question

Secret Message Decoding Problem

Ninja encountered an encoded secret message where each character from 'A' to 'Z' is mapped to a numeric value (A = 1, B = 2, ..., Z = 26). Given a numeric sequence (SEQ) derived from such encoding, determine how many ways the sequence can be decoded back into a valid string.

Input:

The first line contains an integer T representing the number of test cases.
Each test case consists of a single line with a digit sequence.

Output:

For each test case, output the number of ways to decode the provided digit sequence in a separate line.

Example:

Input:

1
121

Output:

Explanation:

Three possible decodings for sequence '121' are 'ABA', 'LA', and 'AU'.

Constraints:

1 <= T <= 10
1 <= N <= 10⁵
0 <= SEQ[i] <= 9

Note:

Input sequence will always have at least 1 valid decoding.
Return the answer modulo 10^9 + 7.
You are not required to print anything as this is handled by the framework. Implement the function logic.

Accepted Answer

The problem involves decoding a numeric sequence back into a valid string based on a given mapping of characters to numeric values.

Use dynamic programming to keep track of the number of ways to decode the sequence at each position.
Consider edge cases such as '0' and '00' which do not have valid decodings.
Handle cases where two digits can be combined to form a valid character (e.g., '12' corresponds to 'L').

Secret Message Decoding Problem

Input:

Output:

Example:

Input:

Output:

Explanation:

Constraints:

Note:

Nagarro Senior Software Engineer interview questions & answers

Popular interview questions of Senior Software Engineer