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

Hello Folks, In this tutorial, we will discuss how to **count possible decodings** of a given **digit sequence in c++** using simple **Recursion** and **Dynamic Programming**. But before that, we have to understand what do we mean by possible decodings, so for that, we will assume 1 as A, 2 as B, 3 as C, and so on. Then possible decoding will be the number of ways in which we can represent a number string by the combinations of these alphabets.

For example;

Given a number string** “1234”** then we can represent it as “ABCD”; “AWD” and “LCD”. So, the possible decodings are** 3**.

Also, note these important points about possible decodings.

- An empty digit sequence has one possible decoding.
- If there are any leading zeros in the given digit sequence then possible decodings are zero.
- If there are more than one zero in between two digits then also possible decodings are zero.
- And the same holds for lagging zeros.

## Methods to Count Possible Decodings of a given Digit Sequence in C++

**Method 1: Recursive Approach**

In this approach, we will set a pointer to the last digit of the numerical strings. Then we will check if the last digit is greater than zero or the last two digits combined is less than equal to 26. If it is true we will repeat the process for the rest of the string till the pointer reaches the position of the first digit minus one. And if not true we will stop iterating further in that branch. And at the last possible decodings will be the count of branches in which the pointer reaches the end successfully. There is a point to be noted here that this recursion tree will follow a **depth-first search **approach during execution.

Look at the following **recursion tree** for better understanding.

Now, look at the code in c++ for this approach.

**Code**

**Code**

#include <iostream> #include <string> using namespace std; // function using recursive approach to find out the number of // possible decodings of the given numerical string int possibleDecodings(string numeric, int size) { // base cases if(size==0){ return 1; } if(numeric[0]=='0'){ return 0; } if(size==1){ return 1; } // initial set int Number_of_decodings=0; // if digits are greater than 0 if(numeric[size-1]-'0'>0){ Number_of_decodings=possibleDecodings(numeric,size-1); } // if digits combined are less than equal to 26 then it will add to the initial count if(numeric[size-2]-'0'==1||(numeric[size-2]-'0'==2&&numeric[size-1]-'0'<=6)){ Number_of_decodings+=possibleDecodings(numeric,size-2); } return Number_of_decodings; } //driver function int main() { //input string string numeric="1234"; int size=numeric.length(); cout<<"Possible decodings are - "<<possibleDecodings(numeric,size); return 0; }

**Time complexity **will be exponential for this case.

**Space complexity** will be** O(1)**.

**Method 2: Dynamic programming Approach**

Now if you will look at the tree carefully then you will observe that in the first branch of the tree, the pointer will be at every location. So, it is better to store the possible decodings at every position there, by which we do not have to calculate them again and again. This process is called **memoization in dynamic programming. **This will reduce the **time complexity** to **O(n)** and will increase the **space complexity** to **O(n)**.

Now, look at the code in c++ to understand it in a better way.

**Code**

**Code**

#include <iostream> #include <string> using namespace std; // function using dynamic programming approach to find out the number of // possible decodings of the given numerical string int possibleDecodings(string numeric, int size) { // array to store number of decodings at every position int Number_of_decodings[size+1]; // base cases Number_of_decodings[0]=1; Number_of_decodings[1]=1; if(numeric[0]=='0'){ return 0; } // sequentially storing the possible decodings for lower sizes upto the original size for(int x=2; x<=size; x++){ // initial set Number_of_decodings[x]=0; // if digits are greater than 0 if(numeric[x-1]-'0'>0){ // using the stored decodings Number_of_decodings[x]=Number_of_decodings[x-1]; } // if digits combined are less than equal to 26 then it will add to the initial count if(numeric[x-2]-'0'==1||(numeric[x-2]-'0'==2&&numeric[x-1]-'0'<=6)){ Number_of_decodings[x]+=Number_of_decodings[x-2]; } } return Number_of_decodings[size]; } //driver function int main() { //input string string numeric="1234"; int size=numeric.length(); cout<<"Possible decodings are - "<<possibleDecodings(numeric,size); return 0; }

**Output**

**Output**

Possible decodings are - 3

This is it for the tutorial. If you have any doubt you can ask them using the comment section.

Also, check out my other blogs.

Peace.

## Leave a Reply