How to print string association from phone number as text?

I need some help with a method i'm writing for a p开发者_C百科roject. 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)

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]);
  }
}

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.

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.

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)

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.

This is an old topic, but anyway..

Recursive solution is really good! But want to present some alternative, let's call it "OOP solution".. :) maybe someone find it useful..

You just need to create some class able to track the state of digit's representation:

private class DigitInLetter {
    private int digit;
    private char[] letters;
    private int currentLetterIndex;

    private DigitInLetter(int digit) {
        this.digit = digit;
        this.letters = pad[digit];//the same pad from recursive solution..
        currentLetterIndex = 0;
    }

    /**
     * Changes selected letter to the next one. If there is no more items  
     * in the array, changes it to one with index 0.
     * 
     * @return true if index reset to 0, otherwise false.
     */
    public boolean changeToNextLetter() {
        if (currentLetterIndex < letters.length-1) {
            currentLetterIndex++;
            return false;
        } else {
            currentLetterIndex = 0;
            return true;
        }
    }

    public char getCurrentLetter() {
        return letters[currentLetterIndex];
    }
}

Having this, you should simply write one line loop to create an array DigitInLetter[] corresponding to given number. And, use the following simple code to iterate all the possibilities:

    int digitIndex = 0;
    while (digitIndex < digitInLetterArray.length) {
        somewhere.add(digitInLetterArray.TO_STRING);//do here whatewer you want.. e.g. some simple toString can be written for DigitInLetter[]... just be careful to do not accumulate tons of references to the same objects being changed.. )) 

        for (digitIndex = 0; digitIndex < digitInLetterArray.length && 
            digitInLetterArray[digitIndex].changeToNextLetter(); digitIndex++);
    }

Some more lines of code in the modeling class, but quite simple in the result..

I was giving an interview today and asked this question. I struggled during an interview but after that I gave it a try and did implement it. here is the Solution in Java.

public static List<String> deriveWordCombinations(String number){

    List<String> finalWord = new ArrayList<String>();
    List<String> iterative = new ArrayList<String>();
    finalWord.add("");
    for(int i=0;i<number.length();i++){
        char c = number.charAt(i);
        String stringForNumber = map.get(c);
        for(String s:finalWord){
            for(char cs: stringForNumber.toCharArray()){
                iterative.add(s+cs);
            }
        }
        finalWord = iterative;
        iterative = new ArrayList<String>();
    }

    return finalWord;
}

static final HashMap<Character,String> map = new HashMap<Character,String>(){
    {
    put('2',"abc");
    put('3',"def");
    put('4',"ghi");
    put('5',"jkl");
    put('6',"mno");
    put('7',"pqrs");
    put('8',"tuv");
    put('9',"wxyz");
    }
};

package LinkedList;

import java.util.ArrayList;
import java.util.LinkedHashMap;

public class letterDigits {

    private static LinkedHashMap<String, String> map;

    private static ArrayList<String> deriveWordCombinations(String number) {

        ArrayList<String> finalWord = new ArrayList<String>();
        ArrayList<String> iterative = new ArrayList<String>();
        finalWord.add("");

        for (int i = 0; i < number.length(); i++) {
            String c = number.substring(i, i + 1);

            String stringForNumber = map.get(c);
            for (String s : finalWord) {
                for (char cs : stringForNumber.toCharArray()) {
                    iterative.add(s + cs);
                }
            }
            finalWord = iterative;
            iterative = new ArrayList<String>();
            System.out.println("Final Word->" + finalWord);
        }

        return finalWord;
    }

    public void makeHashMap() {
        map.put("1", "");
        map.put("2", "ABC");
        map.put("3", "DEF");
        map.put("4", "GHI");
        map.put("5", "JKL");
        map.put("6", "MNO");
        map.put("7", "PQRS");
        map.put("8", "TUV");
        map.put("9", "WXYZ");
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        letterDigits obj = new letterDigits();
        map = new LinkedHashMap<String, String>();
        obj.makeHashMap();
        // System.out.println(map);
        String str = "345";
        ArrayList<String> word = letterDigits.deriveWordCombinations(str);
        System.out.println("Word->" + word);

    }
}

Produces output:

Final Word->[D, E, F]
Final Word->[DG, DH, DI, EG, EH, EI, FG, FH, FI]
Final Word->[DGJ, DGK, DGL, DHJ, DHK, DHL, DIJ, DIK, DIL, EGJ, EGK, EGL, EHJ, EHK, EHL, EIJ, EIK, EIL, FGJ, FGK, FGL, FHJ, FHK, FHL, FIJ, FIK, FIL]
Word->[DGJ, DGK, DGL, DHJ, DHK, DHL, DIJ, DIK, DIL, EGJ, EGK, EGL, EHJ, EHK, EHL, EIJ, EIK, EIL, FGJ, FGK, FGL, FHJ, FHK, FHL, FIJ, FIK, FIL]

for input "345"