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.

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

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

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

#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

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

Your email address will not be published. Required fields are marked *