Results 1 to 4 of 4
 02042015, 12:32 AM #1Member
 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
 02042015, 02:11 AM #2Senior 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
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,
JimThe Java^{TM} Tutorials  SSCCE  Java Naming Conventions
Poor planning on your part does not constitute an emergency on my part
 02042015, 02:41 PM #3
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,422
 Blog Entries
 7
 Rep Power
 28
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,
JosBuild a wall around Donald Trump; I'll pay for it.
 02042015, 03:14 PM #4Just a guy
 Join Date
 Jun 2013
 Location
 Netherlands
 Posts
 5,114
 Rep Power
 12
Re: Recursive solution for interesting number to letter problem
"Syntactic sugar causes cancer of the semicolon."  Alan Perlis
Similar Threads

Loop through all letter and number possibilities?
By Mr.abe90 in forum New To JavaReplies: 11Last Post: 05292011, 07:47 PM 
Interesting CS problem. Need help.
By xtrmi in forum New To JavaReplies: 1Last Post: 05022009, 03:51 AM 
recursive solution for generating all subsets of[1,2,...,n]
By bratzybabe430890 in forum Advanced JavaReplies: 1Last Post: 03172009, 11:26 PM 
Tricky but very interesting problem
By ravjot28 in forum New To JavaReplies: 4Last Post: 06262008, 01:43 PM 
the number of occurrences of each alphabetical letter in the string.
By masaka in forum New To JavaReplies: 20Last Post: 05142008, 09:42 AM
Bookmarks