Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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 6378687.

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?

share|improve this question
    
You forgot Q on 7 and W on 9! –  MrLore Dec 26 '12 at 10:52

1 Answer 1

up vote 4 down vote accepted

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) + "".

share|improve this answer
    
Is recursion the best option for this problem? –  user384706 Dec 25 '12 at 19:06
    
Yes, recursion is IMO a decent way to solve this. –  Duh Dec 25 '12 at 19:09
    
Posted complete code –  user384706 Dec 25 '12 at 19:25
    
Updated my answer, found your bug. –  Duh Dec 25 '12 at 19:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.