Letter Combinations of a Phone Number

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

This is a classic recursive question. Just like the previous question of finding all the combinations of a given array.

Need to notice that 1 and 0 does not correspond to any characters, so handle them seperately

public class Solution {
    HashMap<Character, String> dialMap;
    public void initMap() {
        dialMap = new HashMap<Character, String>();
        dialMap.put('1', "");
        dialMap.put('2', "abc");
        dialMap.put('3', "def");
        dialMap.put('4', "ghi");
        dialMap.put('5', "jkl");
        dialMap.put('6', "mno");
        dialMap.put('7', "pqrs");
        dialMap.put('8', "tuv");
        dialMap.put('9', "wxyz");
        dialMap.put('0', "");
    }
    
    
    public ArrayList<String> letterCombinations(String digits) {
        initMap();
        return search(digits);
    }
    
    public ArrayList<String> search(String digits) {
        ArrayList<String> res = new ArrayList<String>();
        if (digits.length() == 0) {
            res.add("");
            return res;
        }
        if (digits.length() == 1 && (digits.charAt(0) == '1' || digits.charAt(0) == '0'))
            return res;
        char c = digits.charAt(0);
        String temp = dialMap.get(c);
        ArrayList<String> next = letterCombinations(digits.substring(1, digits.length()));
        if (c == '1' || c == '0')
            return next;
        for (int i = 0; i < temp.length(); i++) {
            if (next.isEmpty())
                res.add(new String(new StringBuilder(temp.charAt(i))));
            else {
                for (String s : next) {
                    res.add(new String(temp.charAt(i) + s));
                }
            }
        }
        return res;
    }
}

Second Submission:
The idea is to use recurssion, using a hashmap to store the number pad speed up the checking process.

public class Solution {
    HashMap<Character, String> dialMap;
    public void initMap() {
        dialMap = new HashMap<Character, String>();
        dialMap.put('1', "");
        dialMap.put('2', "abc");
        dialMap.put('3', "def");
        dialMap.put('4', "ghi");
        dialMap.put('5', "jkl");
        dialMap.put('6', "mno");
        dialMap.put('7', "pqrs");
        dialMap.put('8', "tuv");
        dialMap.put('9', "wxyz");
        dialMap.put('0', "");
    }
    
    
    public ArrayList<String> letterCombinations(String digits) {
        initMap();
        return search(digits);
    }
    
    public ArrayList<String> search(String digits) {
        ArrayList<String> res = new ArrayList<String>();
        if  ((digits.length() == 0) || 
            (digits.length() == 1 && (digits.charAt(0) == '1' || digits.charAt(0) == '0'))) { 
            res.add("");
            return res;
        }
        String t = dialMap.get(digits.charAt(0));
        ArrayList<String> next = search(digits.substring(1));
        for (String n : next) {
            for (int i = 0; i < t.length(); i++)
                res.add(t.charAt(i) + n);
        }
        return res;
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s