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

Hello Learners, today we will count the total number of ways a sequence of digits can be decoded using C++ programming language.

Let’s assume that numbers are coded as

A = 1, B = 2, C = 3 , ....... , Z = 26.

Since only 26 alphabets are known A-Z, numbers ranging from 1 to 26 can be converted to corresponding alphabets.

For example:-

1. A sequence of numbers =  “1231”

Possible decodings are   (1, 2, 3, 1) = ABCA , (12, 3, 1) = LCA  and (1, 23, 1) = AWA.  So, “1231” can be decoded in three ways.

2. A sequence of numbers = “1502”

The given a sequence of string can be decoded in zero way because ‘0’ cannot be converted to the alphabet.

C++ Code: Count Possible Decodings of a given Digit Sequence

#include<iostream>
#include<string.h>
using namespace std;

int countDecoding(char *digitSequence, int n)
{
  int count[n+1], a, b;
      count[0] = 1;
      count[1] = 1;
  
  for(int i=1;i<=n;i++)
  {
        if(digitSequence[i-1] == '0')
          {
             return 0;
          }

        else
          {
            a=digitSequence[i]-48;
            b=digitSequence[i-1]-48;
            if(a>0 && a<=26)
                 count[i+1]=count[i];
            if((a + b*10)>0 && (a + b*10) <=26)
                 count[i+1] +=count[i-1];
          }
  }
  return count[n];
}


//Driver function
int main()
{
  char digitSequence[20]; //use array size as per need
  cout<<"Input a sequence of numbers : ";
  cin >> digitSequence;
  int n = strlen(digitSequence);
  cout<<"Total number of decodings possible of the sequence "<<digitSequence<<" are "<<countDecoding(digitSequence,n) << endl;
  return 0;
}