Count Possible Decodings of a given Digit Sequence in Java

Before moving on to the implementation let us have a look at the below example for better clarity.

Examples

Let us consider 'A' represents 1, 'B' represents 2, and so it goes on.

Input : digits[]="123"
Output: 3
//As the possible decodings are "ABC", "LC", "AW"

Input: digits[]="121"
Output: 3
//As the possible dcodings are "ABA", "AU", "LA"

Algorithm

1. Take the input digit sequence
2. Initialize a counting variable count=0
3. If the last digit of the sequence is non-zero then recur for the remaining (n-1) digits sequence and then add the resultant to the total count.
4. If the last and the second last digit form a valid number (or less than 27), repeat the same for the remaining (n-2) digits and sum the result to the total count.

Implementation

Below is the implementation of the above algorithm:

/* Java program to find the possible number of decodings of a given digit sequence */
import java.util.*;
public class Main
{
static int countdecodedigits(char digits[],int n)
{
int count[]=new int[n+1];
count[0]=1;
count[1]=1;
for(int i=2;i<=n;i++){
count[i]=0;
//if last digit is !=0 then digit must be added to the number of words
if(digits[i-1]>'0')
count[i]=count[i-1];

//if second last digit is smaller than 2 and last digit is smaller than 7,then 
//last 2 digits forms a valid character
if(digits[i-2]=='1' ||(digits[i-2]=='2' && digits[i-1]<'7'))
count[i]+=count[i-2];
}
return count[n];
}
//Driven Code
public static void main(String[] args)
{
char digits[]={'1','2','3'};
int n=digits.length;
System.out.println("Possible count of decoding of the sequence: "+countdecodedigits(digits,n));
}
}

Output:

Possible count of decoding of the sequence: 3

Hope this tutorial helps you to better understand the logic behind counting possible decodings of a given Digit Sequence in Java.