class Solution {
private:
    map<int , vector<char> > p = { {2, {'a', 'b', 'c'}},
                                   {3, {'d', 'e', 'f'}},
                                   {4, {'g', 'h', 'i'}},
                                   {5, {'j', 'k', 'l'}},
                                   {6, {'m', 'n', 'o'}},
                                   {7, {'p', 'q', 'r', 's'}},
                                   {8, {'t', 'u', 'v'}},
                                   {9, {'w', 'x', 'y', 'z'}}
                                  };
    vector<string> ph;
public:
    void generate(string digits, string &s, int i){
        if(digits.size() == 0){
            return;
        }
        if(i == digits.size()){
            ph.push_back(s);
            return;
        }
        for(int j = 0; j < p[digits[i] - '0'].size(); j++){
            s.push_back(p[digits[i] - '0'][j]);
            generate(digits, s, i + 1);
            s.pop_back();
        }
        return;
    }
    vector<string> letterCombinations(string digits) {
        string s;
        generate(digits, s, 0);
        return ph;
    }
};