Interview Question
Country: India
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;
}
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.
- Aashish July 02, 2012