How to print string association from phone number as text?

Question

I need some help with a method i'm writing for a project. the method changes a phone number into a list of text strings.

You know that 2-9 have letters associated with them on a phone. i would like to make a converter that will change a 7 digit number to a list of strings. i would like to see all possibilities. i already cut out all the 1's and 0's since they don't have any letters to them. Ex: if our number was only two digits long, 37 would be:

DP DQ DR DS EP EQ ER ES FP FQ FR FS.

So far, i've been trying to use nested for loops, but am not getting the right outputs. any help or ideas would be nice. thanks

(im not asking for full code, but more like suggestions on how to do it)

Answer 1

If I remember correctly, there are no more than 4 letters for any digit.

A crude way of generating is to count up from 0 to 4^(number of digits)-1 in base 4, that would give you numbers like 02031, let the 0 represent the first letter for the relevant digit, 1 for the second and so on. All numbers containing a 3 in a position having a digit that only has 3 letters are discarded.

a 10 digit number will yield a list of over a million base 4 numbers. You have been warned.

edit: A more elegant approach is to look at how many 4 (let's call it x) character digits and 3 (let's call this one y) character digits you have and count from 0 to 4^x*3^y-1. each number can be translated into a sequence of numbers like above by using the / and % operators.

example: if 8 and 9 are the 4 character digits, and you want a list of string representations of the number 258, you count from 0 to 3^2*4-1 = 35. Taking the number 21, for example: Working your way backwards, the rightmost character (from the 8), you get the character by taking

21 % 4 = 1, 1 representing 't'

Dividing away the information from this character you do 21 / 4 = 5.

Next character:

5 % 3 = 2, 2 representing 'l'

5 / 3 = 1.

Final character:

1 % 3 = 1 representing 'b'

This would get you the string "blt".

There are some book-keeping to this algorithm, but you don't get the overhead counting and discarding from the example above, and you don't get the memory overhead that the recursive algorithms have.

Answer 2

You probably want to use recursion. You said not to give you code, so here's just an outline:

// This is the function you're writing.  It prints every possible
// string you can make with the digits of that phone number by
// calling another function recursively.
void printAllPossibilities(String phoneNumber) {
  recursivePrintAllPossibilities("", phoneNumber);
}

void recursivePrintAllPossibilities(String prefix, String phoneNumber) {
  // 1. If the phone number is empty, just print the prefix and return.
  // 2. If the phone number is not empty, take the first digit and convert it
  //   into possible letters.  For each letter, add that letter to the prefix
  //   and then call recursivePrintAllPossibilities with the new prefix, and
  //   with the now-truncated phone number.
}

Given your example input of "37", the main function printAllPossibilities will call recursivePrintAllPossibilities with prefix="" and phoneNumber="37". That function will call itself three times:

1. Once with prefix="D" and phoneNumber="7"
2. Once with prefix="E" and phoneNumber="7"
3. Once with prefix="F" and phoneNumber="7"

The first of those calls will call itself again four times:

1. Once with prefix="DP" and phoneNumber=""
2. Once with prefix="DQ" and phoneNumber=""
3. Once with prefix="DR" and phoneNumber=""
4. Once with prefix="DS" and phoneNumber=""

Each of these calls will just print the prefix. Then control returns one level and does all of the outputs starting with "E", and so on. By the time control is returned to the original function, it will have printed every possibility.

It takes practice to learn to "think" recursively, but in time this will become second nature.

Answer 3

The key to your solution is using the pad array declared in the code below. In a partial phone number 763, for example,

pad[7] will yield the array {'p','q','r'},

pad[6] will yield the array {'m','n','o'},

pad[3] will yield the array {'a','b','c'},

Then, use recursive method getAlpha(int[] num, int next, char[]alpha) to iterate over every combination possibility, forming an algorithmic tree of alphabetic progressions. At each leaf/end node of the tree, is a completed array of alphabets to be appended to the list. Using only one array of alphabets to be reused/overwritten when it recurse back to a previous digit position is possible because the stringified alphabet array is appended only when a leaf/end node is reached. stringify(char[]) not included here.

getAlpha(int[] num) is the entry point method to start from digit position 0 of the recursion. Each recursion level processes the next digit of the phone number.

public class Z{
  // 2D array [i][j]
  // use phone digit as array index i
  final char[][] pad = {
    {'0'},
    {'1'},
    {'a','b','c'},
    {'d','e','f'},
    {'g','h','i'},
    {'j','k','l'},
    {'m','n','o'},
    {'p','q','r'},
    {'s','t','u','v'},
    {'w','x','y','z'},
  };

  // This will be the horrendously long list of possible alphabetic codes
  List<String> combinations = new ArrayList<String>();

  void getAlpha(int[] num, int next, char[]alpha){
    // iterate over all possible alphabets of next digit
    for (int i=0; i<pad[next].length; i++){
      //set,overwrite next cell of array with iterated alphabet
      alpha[next] = pad[next][i];
      if (i<num.length-1)
        //process next next digit
        getAlpha(num, next++, alpha);
      else
        //if end of number
        //append array to horrendously long list
        combinations.add(stringify(alpha));
    }
  }

  public void getAlpha(int[] num){
    getAlpha(num, 0, new char[num.length]);
  }
}

Answer 4

Based on h2g2java's but with the bugs fixed to make it work.

public class Z{
  // 2D array [i][j]
  // use phone digit as array index i
  final char[][] pad = {
    {'0'},
    {'1'},
    {'a','b','c'},
    {'d','e','f'},
    {'g','h','i'},
    {'j','k','l'},
    {'m','n','o'},
    {'p','q','r'},
    {'s','t','u','v'},
    {'w','x','y','z'},
  };

  // This will be the horrendously long list of possible alphabetic codes
  List<String> combinations = new ArrayList<String>();

  void getAlpha(int[] num, int next, char[]alpha){
    // iterate over all possible alphabets of next digit

    for (int i=0; i<pad[num[next]].length; i++){
      //set,overwrite next cell of array with iterated alphabet
      alpha[next] = pad[num[next]][i];
      if (next<num.length-1) {
        //process next next digit
        getAlpha(num, next + 1, alpha);
      } else {
        //if end of number
        //append array to horrendously long list
        combinations.add(String.valueOf(alpha));
      }
    }
  }

  public void getAlpha(int[] num){
    getAlpha(num, 0, new char[num.length]);
  }
}

• when returning from recursion next had been updated when making the previous call so when doing the next iteration of the for loop it is looking up a different number than it should in pad. Rather than incrementing it in the call we just pass the next value.
• Was using the position in the number instead of the number at that position to lookup the chracters in pad array. E.g. if the number was simply 233 it was giving 01a, 01b, 01c instead of add, ade...
• if (i<num.length-1) was wrong. We want to recursively call one time for each digit in the number so its: if (next < num.length-1)
• Changed stringify(alpha) to String.valueOf(alpha)

Answer 5

I assume the ultimate goal of this is to determine which existing words match a given phone number (like phonespell.org). If this is so, you could maybe apply the dictionary you will be using earlier in the process, and avoid having to generate a huge list of nonsensical words first. So in general:

• add all possible letters for the first digit to your solution list
• for the remaining digits:
  • for each solution:
  • remove solution from solution list
  • for each possible letter for the current digit:
    • candidate = solution + letter
    • if there is a dictionary word starting with candidate, add candidate to solution list

You could optimze this by copying all dictionary words still matching your solutions into a new reduced dictionary between each iteration.