17. 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"].

const string alpha[10] = {
    "", " ", "abc", "def", "ghi", "jkl",
    "mno", "pqrs", "tuv", "wxyz"
};
class Solution {
private:
    void dfs(string nums, int level, string sol, vector<string> &ret){
        if(level == nums.size()){
            ret.push_back(sol);
            return;
        }

        int n = nums[level] - '0';
        for(auto &c:alpha[n])
            dfs(nums, level + 1, sol + c, ret);

    }

public:
    vector<string> letterCombinations(string digits) {
        if(digits.empty())  return {};

        vector<string>  res;

        dfs(digits, 0, "", res);
        return res;
    }
};