CareerCup

Here is a recursive one.
The idea is very simple. If we know the number of solutions for n-1 characters, we can extend it for n characters. How? Lets see.
Say the number of solutions for n-1 characters is p, then if by combining n-1th character with nth character gives an integer <=26, it also leads to another possible solution.\
Based on same idea, here is the simple code.

#include <stdio.h>
#include <string.h>
int count_decode(char s[10],int n)
{
    int x1,x2,z,res;
    if(n<0)
        return -1;
    if(n==0)
        return 1;
    else
    {
        res= count_decode(s,n-1);
        x1=s[n]-'0',x2=s[n-1]-'0';
        z=x2*10 + x1;
        return (z<=26?(res+1):res);
    }
}
int main()
{
    int i,j,n;
    char S[10];
    gets(S);
    n=strlen(S);
    printf("< %d >",count_decode(S,n-1));
return 0;
}

one possible recursive solution is...

#include <stdio.h>
#include <string.h>

int combination(int *temp, int start, int end)
{
int i;
if( start >= end)
return 1;
int l=0,k=0;
l = combination(temp, start+1, end);

if( (start + 1) < end && (temp[start]*10 + temp[start+1]) <= 26)
k = combination(temp, start+2, end);

return l+k;
}

int main()
{
char string[]="12512";
int temp[strlen(string)+1];
int i;
for(i=0; i<strlen(string); i++)
temp[i]=string[i]-48;
printf("%d\n", combination(temp, 0, strlen(string)));
return 0;
}

/* The character 'a' to 'z' are encoded as 1 - 26. Given a string of digits,
compute the number of valid decodings of the string. For example,
both 'aa' and 'k' can be encoded as '11'. Hence num_valid_encodings('11') = 2. */

//      WORKING CODE   ||       recursive

#include <stdio.h>
#include <string.h>
int count_decode(char S[10],int n)
{
    int x1=S[n-1]-'0',x2=S[n-2]-'0',z;
    if(!n)
        return 0;
    else if(n==1)
    {
        return 1;
    }
    else
    {
        z=x2*10+x1;
      //  printf("z=%d ",z);
        if(z>26)
            return (count_decode(S,n-1));
        else if(n==2)
            return (count_decode(S,n-1) + count_decode(S,n-2)+1);
        else
            return (count_decode(S,n-1) + count_decode(S,n-2));
    }
}
int main()
{
    int i,j,n;
    char S[10];
    gets(S);
    n=strlen(S);
    printf("< %d >",count_decode(S,n));
return 0;
}

tell me if u find wrong answer

Let F(n) be number of ways of decoding till n th index.

Initialize F(0) and F(1) with appropriate values

for i =2 to length of string
{
F(i) = F(i-1) + F(i-2) if 10* a[i-2] + a[i-1] < = 26

else
F(i) = F(i-1)
}
}

I have modified the code & it prints the encodings too.

#include <stdio.h>
 
void encoding(char *s,char *str,int depth)
{
        int i;
        if(*s=='\0')
        {
                str[depth]='\0';
                printf("%s\n",str);
        }
        else
        {
                str[depth]=*s-48 + 64;
                encoding(s+1,str,depth+1);
                
                if(*(s+1)!='\0')
                {
                        i=( (str[depth]-64)*10 + (*(s+1)-48) );
                        if(i<=26)
                        {       str[depth]=i+64;
                                encoding(s+2,str,depth+1);
                        }
                }
        }
}
 
int main()
{
        char s[]="12121",str[10];
        encoding(s,str,0);
        return 0;
}

ideone.com/1MIff

int countCombinations(const string &str,int start)
{
        int count=0;
        cout << "\nIndex = " << start;
        if (str.length()-start==2)
        {
                cout << "\nHitting base condition " ;
                count+=2;
                cout << "\n" << start <<"." << str[start] << "\n" << start+1 << "." << str[start+1];
                int number=(str[start]-48)*10;
                number=number+(str[start+1]-48);
                if (number > 0 && number < 26)
                {
                        count++;
                        cout << "\n" <<str[start] << str[start+1];
                }
                return count;
        }
        if (str.length()-start > 2)
        {
                count=1;
                cout << "\n" << start << "." << str[start];
                count=count+countCombinations(str,start+1);
                //countCombinations(str,start+1);
                int number=(str[start]-48)*10;
                number=number+(str[start]-48);
                if (number > 0 && number < 26)
                {
                        cout << "\n" <<str[start] << str[start+1];
                        count=count+countCombinations(str,start+2);
                }
                return count;
        }
}

int combo(string state, string in)
{
     if (in.isempty())
          return 1;

     return combo(state.append(in[0]), in.substr(1, in.length)) + 
               (in.length>1 && atoi(n.substr(0,2)) < 27)?
               combo(state.append(in.substr(0,2)), in.substr(2, in.length)) : 0;
}