Count Possible Decodings of a given Digit Sequence in C++

We are given a string representing a digit sequence. Each digit is decoded from 1 to 26 as English Alphabet. 1 is ‘A’, 2 is ‘B’ and so on till 26 as ‘Z’. The goal is to find the count of all possible decodings out of a given digit sequence. If the sequence is ‘123’ then possible decodings are ‘ABC’ ( 1-2-3 ), ‘LC’ (12-3), ‘AW’ (1-23). Count is 3.

Let us understand with examples.

Input − str[]=”1532”

Output − Count of Possible Decodings of a given Digit Sequence are − 2

Explanation − Possible decodings are AECB - (1-5-3-2) and OCB (15-3-2).

Input − str[]=”216”

Output − Count of Possible Decodings of a given Digit Sequence are − 3

Explanation − Possible decodings are “BAF” ( 2-1-6 ), “UF” ( 21-6 ), “BP” ( 2-16 )

The approach used in the below program is as follows

We will do this using a recursive method. Pass portions of string to this recursive method.

Check if the last digit is not ‘0’ if true, check the rest of the string between 0 and length-1. Check if the last two digit string portion makes a number between 1 and 26. If true, update count and check the rest of the string between 0 and length-2.

• We are taking the input as string str[].

• Function decode_digit_seq(char *str, int length) takes the string and its length and returns count of possible decodings of str.

• If length is 0. Return 1.

• If length is 1. Return 1.

• If last single character is non-zero, count will be decode_digit_seq(str, int length-1)

• If the second last character is 1 then last two digits would be between 10 and 19 (J to S ), update count as count = count + decode_digit_seq(str, length-2)

• If second last character is 2 and last character is <7 then last two digits would be between 20 and 26 (T to Z), update count as count = count + decode_digit_seq(str, length-2)

• Now all cases are taken.

• In the end after all recursions return count as result.

Example

 Live Demo

#include <iostream> #include using namespace std; int decode_digit_seq(char *str, int length){    int count = 0;    if(length == 0){       return 1;    }    if(length == 1){       return 1;    }    if(str[0] == '0'){       return 0;    }    if(str[length-1] > '0'){       count = decode_digit_seq(str, length-1);    }    if(str[length-2] == '1'){       count = count + decode_digit_seq(str, length-2);    }    if(str[length-2] == '2' && str[length-1] < '7'){       count = count + decode_digit_seq(str, length-2);    }    return count; } int main(){    char str[] = "7651";    int length = strlen(str);    cout<<"Count of Possible Decodings of a given Digit Sequence are: "<< decode_digit_seq(str, length);    return 0; }

Output

If we run the above code it will generate the following output −

Count of Possible Decoding of a given Digit Sequence are: 1