3.7. Combinatorics

3.7.1. Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent in the following phone input pad. Return the answer in any order.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

     +---------+--------+---------+
     | 1       | 2(abc) | 3(def)  |
     +---------+--------+---------+
     | 4(ghi)  | 5(jkl) | 6(mno)  |
     +---------+--------+---------+
     | 7(pqrs) | 8(tuv) | 9(wxyz) |
     +---------+--------+---------+
     |  *(+)   |  0(-)  |  ^(#)   |
     +---------+--------+---------+

Example:
Input: digits = "23"; Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

---

struct sloution{
    vector<string> letterCombinations(string d) {
        vector<string> r;
        string p;
        vector<string> = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        dfs(r, p, d, m, 0);
        return r;
    }
    // edge case: d="" --> [], d="111" --> [] !!!
    void dfs(vector<string>& r, string& p, string& d, vector<string>& m, int k){
        if(d.size()==k){ // Cannot use p!!!
            if(!p.empty()) r.push_back(p);
            return;
        }
        for(char c: m[d[k]-'0']){
            p+=c;
            dfs(r,p,d,m,k+1);
            p.pop_back();// backtrack in the graph, unwind the stack
        }
    }
};