## Problem Link

http://www.spoj.com/problems/ACODE/

## Problem Description

Alice and Bob send secret encoded messages to each other. The encoding scheme is: Letter ‘A’ is assigned codeword 1, ‘B’ is assigned codeword 2, and so on down to ‘Z’ being assigned 26.

Note: Only capital letters are used in the input.

Now, the encoded message can be decoded in various ways. For example, 25114 can be decoded as ‘BEAN’, ‘BEAAD’, ‘YAAD’, ‘YAN’, ‘BEKD’.

So, we need to find number of various possible decodings possible of a given encoded numeric string.

## Concepts Used

Dynamic Programming

## Code

```
#include<bits/stdc++.h>
using namespace std;
int main()
{
while(1) {
char str[5005];
scanf("%s",str); //input
if(str[0]=='0') { //if input 0 then break(according to question)
break;
}
long long int dp[5005]; //declare an array of 5005 size as number of digits in string could be atmost 5005
int len=strlen(str);
for(int i=0;i<5005;i++) {
dp[i]=0; //initializing the array elements to zero
}
dp[0]=1; //initializing the base case as any string of length 1 will have only 1 possible decoding
long long int x;
for(int i=1;i<len;i++) {
x=(str[i-1]-'0')*10+(str[i]-'0'); //calculating x as number formed by considering 2 consecutive characters of the string(current and previous)
if(str[i]-'0') { //if current character is not '0' then dp[i]=dp[i-1], as 0 has no independent existence
dp[i]=dp[i-1];
}
if(x>=10 && x<=26) { //if 10<=x<=26 then string can have different encodings else only 1
if(i>=2) { //if i>=2 then dp[i]=dp[i]+dp[i-2] as we formed x by current and previous character
dp[i]+=dp[i-2];
}
else { //if i<2 then dp[i]=dp[i]+1 eg:"23", dp[0]=1 and dp[1]=1+1=2
dp[i]+=1;
}
}
}
printf("%lld\n",dp[len-1]); //printing the answer
}
return 0;
}
```

## Explanation

The problem is a linear dynamic programming problem.

If we consider a single digit number say a(=str[i]), the answer would be `dp[i]=dp[i-1]`

if the digit is non zero.

If we consider a two digit number say c(=str[i-1]×10+str[i]), then if 10<=c<=26, the answer would be `dp[i]+=dp[i-2]`

. (If i is less than 2 , then answer would be `dp[i]+=1`

)

We cannot consider a three digit number as it would obviously be greater than 26.

For example, consider “25114”

1. i=0, str[i]=’2′ ->dp[0]=1.

2. i=1, str[i]=’5′, x=2×10+5=25(10<=x<=26) -> dp[1]=dp[0]+1=1+1=2.

3. i=2, str[i]=’1′, x=5×10+1=51(x out of range) -> dp[2]=dp[1]=2.

4. i=3, str[i]=’1′, x=1×10+1=11(10<=x<=26) -> dp[3]=dp[2]+dp[1]=2+2=4.

5. i=4, str[i]=’4′, x=1×10+4=14(10<=x<=26) -> dp[4]=dp[3]+dp[2]=4+2=6.

6 is the answer.

This content has been helpful to you?

Thanks for contributing!