Day 29, 17, Letter Combinations of a Phone Number

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.
-------------------------------------------------------------------
There's a better solution - recursive permutation

class Solution {
public:

    vector<string> recur (string digits, unordered_map<char,string> &k) {
        if (digits.length() == 1) {
            vector<string> start;
            for (int i=0;i<k[digits[0]].length();i++) {
                string temp;
                temp += k[digits[0]][i];
                start.push_back(temp);
            }
            return start;
        }
        vector<string> t = recur(digits.substr(0,digits.length()-1),k);
        vector<string> ret;
        for (int i=0;i<t.size();i++) {
            for (int j=0;j<k[digits.back()].length();j++) {
                string str = t[i] + k[digits.back()][j];
                ret.push_back(str);
            }
        }
        return ret;
    }


    vector<string> letterCombinations(string digits) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<string> ret;
        if (digits == "") {
            ret.push_back("");
            return ret;
        }
        unordered_map<char,string> k;
        k['2'] = "abc"; 
        k['3'] = "def";
        k['4'] = "ghi";
        k['5'] = "jkl";
        k['6'] = "mno";
        k['7'] = "pqrs";
        k['8'] = "tuv";
        k['9'] = "wxyz"; 
        return recur(digits,k);

    }
};

Update on Sep-10-2014
refactoried, use index

class Solution {
public:
    void rec (vector<string> &rt, string str, string digits, int index, unordered_map<char,string> &k) {
        if (index == digits.length()) {
            rt.push_back(str);
            return;
        }
        char digit = digits[index];
        string letters = k[digit];
        for (int i = 0; i < letters.length(); i++) {
            rec(rt,str + letters[i],digits,index + 1,k);
        }
        
    }


    vector<string> letterCombinations(string digits) {
        vector<string> rt;
        if (digits.length() == 0) {
            rt.push_back("");
            return rt;
        }
        
        unordered_map<char,string> k;
        k['2'] = "abc";
        k['3'] = "def";
        k['4'] = "ghi";
        k['5'] = "jkl";
        k['6'] = "mno";
        k['7'] = "pqrs";
        k['8'] = "tuv";
        k['9'] = "wxyz"; 
        
        rec(rt,"",digits,0,k);
        return rt;
    }
};

Update on Jan-19-2015
BFS

class Solution {
public:
    unordered_map<char,string> letters;
    vector<string> rt;
    
    void bfs(string digits) {
        for (int i = 0; i < digits.length(); i++) {
            string st = letters[digits[i]];
            vector<string> cpRt;
            
            for (int j = 0; j < st.length(); j++) {
                vector<string> cp = rt;
                for (int k = 0; k < cp.size(); k++) {
                    cp[k] = cp[k] + st[j];
                }
                cpRt.insert(cpRt.end(),cp.begin(),cp.end());
            }
            rt = cpRt;
        }
    }

    vector<string> letterCombinations(string digits) {
        letters['1'] = "";
        letters['2'] = "abc";
        letters['3'] = "def";
        letters['4'] = "ghi";
        letters['5'] = "jkl";
        letters['6'] = "mno";
        letters['7'] = "pqrs";
        letters['8'] = "tuv";
        letters['9'] = "wxyz";
        letters['0'] = " ";
        
        rt.push_back("");
        bfs(digits);
        return rt;
    }
};

Java

public class Solution {
    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) return new ArrayList<>();
        
        Map<Character, String> map = getDigitsMap();
        List<String> rt = new ArrayList<>();
        rt.add("");
        
        for (int i = 0; i < digits.length(); i++) {
            rt = appendNewChar(map.get(digits.charAt(i)), rt);    
        }
        
        return rt;
    }
    
    private List<String> appendNewChar(String source, List<String> rt) {
        List<String> newRt = new ArrayList<String>();
        for (String s : rt) {
            for (int i = 0; i < source.length(); i++) {
                newRt.add(s + Character.toString(source.charAt(i)));
            }
        }
        
        return newRt;        
    }

    private Map<Character, String> getDigitsMap() {
        Map<Character, String> map = new HashMap<>();
        map.put('0',"");
        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");
        
        return map;
    }
}

Recursion

public class Solution {
    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) return new ArrayList<>();
        
        Map<Character, String> map = getDigitsMap();
        List<String> rt = new ArrayList<>();
        rec(map, rt, "", digits, 0);
        
        return rt;
    }
    
    private void rec(Map<Character, String> map, List<String> rt, String comb, String digits, int index) {
        if (index == digits.length()) {
            rt.add(comb);
            return;
        }
        
        String source = map.get(digits.charAt(index));
        for (int i = 0; i < source.length(); i++) {
            rec(map, rt, comb + Character.toString(source.charAt(i)),  digits, index + 1);
        }
    }

    private Map<Character, String> getDigitsMap() {
        Map<Character, String> map = new HashMap<>();
        map.put('0',"");
        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");
        
        return map;
    }
}