Recursion to map phone number to strings

Question

I am trying to solve the following via recursion: In a phone we have each digit mapped to a number.

Example:

1 2(ABC) 3(DEF) 
4(GHI) 5(JKL) 6(MNO) 
7(PRS) 8(TUV) 9(XYZ) 
* 0 # 

I need to print out all the possible sequences of a phone number (example: 637-8687).

I did the following that seems to solve it:

static Map<String, String> digits; 
 static{ 
 digits = new HashMap<String, String>(); 
 digits.put("2", "ABC"); 
 digits.put("3", "DEF"); 
 digits.put("4", "GHI"); 
 digits.put("5", "JKL"); 
 digits.put("6", "MNO"); 
 digits.put("7", "PRS"); 
 digits.put("8", "TUV"); 
 digits.put("9", "XYZ"); 
 } 
 public static void printSequences(String phoneNumber, Map<String, String> associations){ 
 if(phoneNumber == null || phoneNumber.isEmpty()){ 
 throw new IllegalArgumentException(); 
 } 
 if(associations == null || associations.isEmpty()){ 
 throw new IllegalArgumentException(); 
 } 
 String[] letters = new String[phoneNumber.length()]; 
 for(int i = 0; i < phoneNumber.length(); i++){ 
 String seq = associations.get(phoneNumber.charAt(i) + ""); 
 if(seq == null)continue; 
 letters[i] = seq; 
 } 
 printSequences(letters, 0, letters.length, ""); 
 } 
private static void printSequences(String[] letters, int start, int end, String prefix) { 
 if(start == end){ 
 System.out.println(prefix); 
 return; 
 } 
 String sequence = letters[start]; 
 if(sequence == null) 
 return; 
 for(int i = 0; i < sequence.length(); i++){ 
 printSequences(letters, start + 1, end, prefix + sequence.charAt(i)); 
 } 
 } 

The String[] letters has all the relevant digits (extracted from a Map). In this case it is [MNO, DEF, PRS, TUV, MNO, TUV, PRS] for phone [phone].

This code seems to work but does not for 637-8687. For 637-8687 it actually prints nothing at all!

I am trying to practice recursion, so could you please help me out with this one? Also, is recursion actually the best approach on such a problem?

• MrLore: You forgot Q on 7 and W on 9!

Answer 1

Here are some comments from my side:

1. The end parameter is unnecessary. You can just test for start >= letters.length instead. Also, you might want to rename start.

2. It might make sense to wrap your algorithm in a callable method such as private void printSequences(String[] letters), which just kicks off the recursion by calling printSequences(letters, 0, "").

3. As to your bug, it depends on how exactly you are calling the method above (what is start and end).

4. Your test for letters[start] == null does not seems necessary if the letters array is well-behaved (i.e., does not contain null).

5. Recursion is a decent way to solve this problem.

6. Your bug comes from the fact that when you process "-" as a digit, you generate null in letters. When processing letters, you don't call your function recursively but just return. That way, nothing is ever printed, which explains the behavior you describe. The proper way to handle that case would be to call the method recursively without appending anything to the prefix (or to make sure there are no null entries in letters, which I believe is the better way, see point 7).

7. I would use a List<String> for letters. That way you don't end up with null entries.

8. Your IllegalArgumentException should describe the problem. For instance, it could say "Got illegal phoneNumber".

9. Your digits map should map characters to strings, not strings to strings. That way you don't have to coerce the character into string with phoneNumber.charAt(i) + "".

• user384706: Is recursion the best option for this problem?
• Dino: Yes, recursion is IMO a decent way to solve this.
• user384706: Posted complete code
• Dino: Updated my answer, found your bug.