Problem
There is a coding system where all the letters in an Alphabet is coded into a number such as a-->1, b-->2,..., z-->26. Given an array of the integers, the program should output the number of possible letter arrangements in the decoded string.
C++ Program
#include<iostream>
using namespace std;
#define SIZE 4
int getCount(int A[SIZE],int s)
{
if(s>=SIZE - 1)
{
return 1;
}
else
{
if(A[s]*10 + A[s+1] <= 26)
{
return getCount(A,s+1) + getCount(A,s+2);
}
else if(A[s] <= 26)
{
return getCount(A,s+1);
}
else
{
return 0;
}
}
}
int main()
{
//int A[SIZE]={1,2,6,1,2,4};
int A[SIZE]={1,1,2,3};
int s=0;
cout<<"Recursive: "<<getCount(A,s)<<endl;
int a=1;
int b=1;
int ans=a;
int n=SIZE;
if(10*A[n-2]+A[n-1] <= 26)
{
a=2;
}
for(int i=n-3; i>=0; i--)
{
if(10*A[i]+A[i+1] <= 26)
{
ans=a+b;
b=a;
a=ans;
}
else
{
ans=a;
b=a;
}
}
cout<<"Dynamic Programming: "<<ans<<endl;
}
Output
Recursive: 5
Dynamic Programming: 5
Process returned 0 (0x0) execution time : 0.018 s
Press any key to continue.
