Wednesday, 4 July 2012

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.

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; }

2 comments:

  1. Hi,

    why do u have "count_decode(S,n-2)" in n==2 condition when it is only returning 0.

    but when we remove this from code then it doesn't work. Can u please explain me why ?

    ReplyDelete
  2. Hi,

    i got the solution....

    no need to call any function in case of 2

    just return 2

    public static int count_decode(char S[],int n)
    {
    if(n == 0)
    return 0;
    if(n==1)
    {
    return 1;
    }
    int x=S[n-1]-'0',y=S[n-2]-'0',numFormed;


    numFormed = y*10 + x;

    if(numFormed > 26)
    return (count_decode(S,n-1));
    if(n==2)
    return 2;
    else
    return (count_decode(S,n-1) + count_decode(S,n-2));

    }

    ReplyDelete