class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> res;
        if (digits.size() == 0) {
            return res;
        }
        int start = 0;
        string curStr = "";
        helper(start, digits,curStr, res);
        return res;
    }
    void helper(int start, string digits, string& curStr, vector<string>& res) {
        if (start == digits.size()) {
            res.emplace_back(curStr);
            return;
        }
        // 2、根据当前数字获取能选择的字母列表
        auto curValueList = keyValue[digits[start]];
        // 3、在当前可供选择的字母里面进行选择
        for (auto curValue : curValueList) {
            string temp = curStr;
            curStr += curValue;
            helper(start + 1, digits, curStr, res);
            curStr = temp;
        }
    }
private:
    // 1、map存储数字与字母的对应关系(选择列表)
    unordered_map<int, vector<string>> keyValue = {
        {'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"}},
    };
};