SPOJ: ACODE-Alphacode

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!

Yes No