Results 1 to 4 of 4
  1. #1
    Join Date
    Feb 2011
    Posts
    9
    Rep Power
    0

    Default 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. #2
    jim829 is offline Senior Member
    Join Date
    Jan 2013
    Location
    Northern Virginia, United States
    Posts
    6,226
    Rep Power
    14

    Default Re: Recursive solution for interesting number to letter problem

    Quote Originally Posted by Silversurfer20 View Post
    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
    The JavaTM Tutorials | SSCCE | Java Naming Conventions
    Poor planning on your part does not constitute an emergency on my part

  3. #3
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    14,422
    Blog Entries
    7
    Rep Power
    28

    Default 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
    Build a wall around Donald Trump; I'll pay for it.

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

    Default Re: Recursive solution for interesting number to letter problem

    Quote Originally Posted by Silversurfer20 View Post
    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.
    "Syntactic sugar causes cancer of the semicolon." -- Alan Perlis

Similar Threads

  1. Loop through all letter and number possibilities?
    By Mr.abe90 in forum New To Java
    Replies: 11
    Last Post: 05-29-2011, 07:47 PM
  2. Interesting CS problem. Need help.
    By xtrmi in forum New To Java
    Replies: 1
    Last Post: 05-02-2009, 03:51 AM
  3. recursive solution for generating all subsets of[1,2,...,n]
    By bratzybabe430890 in forum Advanced Java
    Replies: 1
    Last Post: 03-17-2009, 11:26 PM
  4. Tricky but very interesting problem
    By ravjot28 in forum New To Java
    Replies: 4
    Last Post: 06-26-2008, 01:43 PM
  5. Replies: 20
    Last Post: 05-14-2008, 09:42 AM

Posting Permissions

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