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

Input:Digit string “23”
Output: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].
Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

Thoughts:
Another classic recursion problem. We try to generate solution each time by iterating through every digit and every character that digit maps to. If we overflow, we cut that solution and stop. If we get the correct solution (where solution.length() == digits.length()), we add to the solution set.

Code (Java):

public class Solution {
    private HashMap<Character, String> map;
    
    public ArrayList<String> letterCombinations(String digits) {
        setup();
        ArrayList<String> solutions
            = new ArrayList<String>();
        recursion(digits, 0, new String(), solutions);
        return solutions;
    }
    
    private void recursion(String digits, int start, 
        String sol, ArrayList<String> solutions) {
        if(sol.length() > digits.length()) {
            return;  
        } else if(sol.length() == digits.length()) {
            solutions.add(sol);
            return;
        } else {
            for(int i = start; i < digits.length(); ++i) {
                String letters = map.get(digits.charAt(i));
                for(int j = 0; j < letters.length(); ++j) {
                    recursion(digits, i + 1, sol + letters.charAt(j), solutions);
                }
            }
        }
    }
    
    private void setup() {
        map = new HashMap<Character, String>();
        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");
        map.put('0', " ");
    }
}

Code (C++):

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        setup();
        vector<string> solutions;
        string s;
        recursion(digits, 0, s, solutions);
        return solutions;
    }
    
private:
    map<char, string> mapping;
    void recursion(string digits, int start, 
        string sol, vector<string>& solutions) {
        if(sol.size() > digits.size()) {
            return;  
        } else if(sol.size() == digits.size()) {
            solutions.push_back(sol);
            return;
        } else {
            for(int i = start; i < digits.size(); ++i) {
                string letters = mapping[digits[i]];
                for(int j = 0; j < letters.size(); ++j) {
                    recursion(digits, i + 1, sol + letters[j], solutions);
                }
            }
        }
    }
    
    void setup() {
        mapping.clear();
        mapping['1'] = "";
        mapping['2'] = "abc";
        mapping['3'] = "def";
        mapping['4'] = "ghi";
        mapping['5'] = "jkl";
        mapping['6'] = "mno";
        mapping['7'] = "pqrs";
        mapping['8'] = "tuv";
        mapping['9'] = "wxyz";
        mapping['0'] = " ";
    }
};
Advertisements

2 Comments (+add yours?)

  1. Nader
    Oct 21, 2012 @ 12:07:19

    The following loop is not necessary:
    for(int i = start; i < digits.size(); ++i) { […] }
    Even though it does return the correct result. See the following link for a variation of the code above without the loop: http://pastebin.com/qJc5nSvE
    Regards. And thanks again for this awesome blog.

    Reply

  2. Nankai
    Jan 26, 2013 @ 17:32:23

    The program is not correct if you have this loop:
    for(int i = start; i < digits.size(); ++i) { […] }

    Reply

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

%d bloggers like this: