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.

class Solution {
public:
    void LC(string digits, map<char, string> mp, vector<string>& sol) {
        for (int i = 0; i < digits.size(); i++) {
            string letter = mp[digits[i]];
            int sol_size = sol.size();
            vector<string> tmp;
            for (int k = 0; k < sol_size; k++) {
                for (int j = 0; j < letter.size(); j++) {
                    tmp.push_back(sol[k] + string(1, letter[j]));
                }
            }
            sol = tmp;
            tmp.clear();
        }
        return;
    }
 
    vector<string> letterCombinations(string digits) {
        vector<string> sol;
     
        if (digits.empty()) {
            return sol;
        }
        sol.push_back("");
     
        map<char,string> mp;
        mp['1'] = "";mp['0'] = "";
        mp['2'] = "abc";mp['3'] = "def";mp['4'] = "ghi";mp['5'] = "jkl";
        mp['6'] = "mno";mp['7'] = "pqrs";mp['8'] = "tuv";mp['9'] = "wxyz";
     
        LC(digits, mp, sol);
        return sol;
    }
};




==== online backtracking =====

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> lettComb;
        string dict[] = {" ", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        string comb(digits.size(),'\0');
        findLettComb(digits, 0, dict, comb, lettComb);
        return lettComb;
    }
    
    void findLettComb(string &digits, int index, string dict[], string &comb, vector<string> &lettComb) {
        if(index==digits.size()) {
            lettComb.push_back(comb);
            return;
        }
        
        string lett= dict[digits[index] - '0'];
        for(int i=0; i<lett.size(); i++) {
            comb[index] = lett[i];
            findLettComb(digits, index+1, dict, comb, lettComb);
        }
    }
};