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 of phone number: 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
add comment

1 Answer

up vote 4 down vote accepted

Here are some comments from my side

1) Theendparameter is unnecessary. You can just test forstart >= letters.lengthinstead. Also, you might want to rename start.

2) It might make sense to wrap your algorithm in a callable method such asprivate 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 forletters[start] == nulldoes not seems necessary if thelettersarray is well-behaved (i.e., does not containnull).

Edit: couple more comments

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 generatenullinletters. When processingletters,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 inletters, which I believe is the better way, see point 7).

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

8) YourIllegalArgumentExceptionshould describe the problem. For instance, it could say "Got illegal phoneNumber".

9) Yourdigitsmap 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
add comment

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.