# Thread: Recursive solution for interesting number to letter problem

1. Member
Join Date
Feb 2011
Posts
9
Rep Power
0

## Recursive solution for interesting number to letter problem

I recently came across a problem that I'm trying to find a recursive solution to, and am hoping people here can help. Everything I try fails at least one test case:

Imagine a system where numbers correspond to letters, so 1 = a, 2 = b etc... right on up through the alphabet until 26 = z. This means if I give you a string of digits "1", it obviously corresponds to the letter a. However if I give you "11", it could correspond to "a", or to "k" because k is the 11th letter. In this way "111" could represent "aaa","ka" or "ak" and so on. 0's further complicate the problem because "0" itself doesn't correspond to a letter, but "10" corresponds to "j", so that also has to be taken into account.

Code a method which takes a string of digits and calculates the number of possible permutations of letters that can be obtained from that string. So the above example of "111" would result in 3.

Here are the test cases:

Java Code:
```assertEquals(2, letterPermutationCounter.countPermutations("11")); // aa | k
assertEquals(3, letterPermutationCounter.countPermutations("111"));   // ak | ka | aaa
assertEquals(5, letterPermutationCounter.countPermutations("1111"));  // aak | kaa | aka | kk | aaaa
assertEquals(8, letterPermutationCounter.countPermutations("11111"));  // aaka | kaaa | akaa | kka | aaaaa | akk | kak | aak
assertEquals(2, letterPermutationCounter.countPermutations("1011"));  // jaa | jk
assertEquals(4, letterPermutationCounter.countPermutations("2611"));  // zk | zaa | bfk | bfaa
assertEquals(2, letterPermutationCounter.countPermutations("2711"));  // bfaa | bfk```

2. Senior Member
Join Date
Jan 2013
Location
Northern Virginia, United States
Posts
6,226
Rep Power
14

## Re: Recursive solution for interesting number to letter problem

Originally Posted by Silversurfer20
I recently came across a problem that I'm trying to find a recursive solution to, and am hoping people here can help. Everything I try fails at least one test case:

Imagine a system where numbers correspond to letters, so 1 = a, 2 = b etc... right on up through the alphabet until 26 = z. This means if I give you a string of digits "1", it obviously corresponds to the letter a. However if I give you "11", it could correspond to "a", or to "k" because k is the 11th letter. In this way "111" could represent "aaa","ka" or "ak" and so on. 0's further complicate the problem because "0" itself doesn't correspond to a letter, but "10" corresponds to "j", so that also has to be taken into account.

Code a method which takes a string of digits and calculates the number of possible permutations of letters that can be obtained from that string. So the above example of "111" would result in 3.

Here are the test cases:

Java Code:
```assertEquals(2, letterPermutationCounter.countPermutations("11")); // aa | k
assertEquals(3, letterPermutationCounter.countPermutations("111"));   // ak | ka | aaa
assertEquals(5, letterPermutationCounter.countPermutations("1111"));  // aak | kaa | aka | kk | aaaa
assertEquals(8, letterPermutationCounter.countPermutations("11111"));  // aaka | kaaa | akaa | kka | aaaaa | akk | kak | aak
assertEquals(2, letterPermutationCounter.countPermutations("1011"));  // jaa | jk
assertEquals(4, letterPermutationCounter.countPermutations("2611"));  // zk | zaa | bfk | bfaa
assertEquals(2, letterPermutationCounter.countPermutations("2711"));  // bfaa | bfk```
You are not doing permutations (at least not what I know as permutations). If you were, the last one would be bfaa, bfk, fbaa, fbk, aafb, aabf, ... and so forth. Looks to me like you are simply scanning left to right and seeing how many different ways the string can be interpreted based on your stated mapping.

And I don not know what you expect from this post since you have not provided any code nor ask a specific question.

Regards,
Jim

3. ## Re: Recursive solution for interesting number to letter problem

Nice little problem;my solution nibbles one possible letter from the left and solves the rest of the problem by invoking recursively and appending the one letter to all elements of the found solution. It returns the entire solution. If the String is empty, the solution contains one empty String and if the input String starts with a '0', there is no solution, so the method returns null.

kind regards,

Jos

4. Just a guy
Join Date
Jun 2013
Location
Netherlands
Posts
5,114
Rep Power
12

## Re: Recursive solution for interesting number to letter problem

Originally Posted by Silversurfer20
Everything I try fails at least one test case:
So post such an attempt you did. I hope you ask this to figure out where you are wrong rather than having other provide a solution to you.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•