力扣17. 电话号码的字母组合

深度优先搜索

• 思路：
  • 每个电话号码数字对应了多个字母可以看成是树的节点；
  • 下一个数字对应的字母是下一层的节点，整体可以看成一颗多叉树；
  • 结果需要进行深度优先遍历，从根节点到叶子结点；
  • 数字对应的字符串，每次选择一个出来，依次与下个数字对应的一个字母结合，直到叶子结点；
  • 然后再弹栈返回上一层分支继续遍历；

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

        initPhoneMap();

        std::string combination;
        dfs(results, digits, 0, combination);

        return results;
    }


private:
    void dfs(std::vector<std::string>& results, 
        const std::string& digits,
        int index,
        string& combination) {
        if (index == digits.size()) {
            results.push_back(combination);
            return;
        }

        char number = digits[index];
        const std::string& letters = phoneMap_.at(number);
        for (const char& letter: letters) {
            combination.push_back(letter);
            dfs(results, digits, index + 1, combination);
            combination.pop_back();
        }
    }

    void initPhoneMap() {
        phoneMap_['2'] = "abc";
        phoneMap_['3'] = "def";
        phoneMap_['4'] = "ghi";
        phoneMap_['5'] = "jkl";
        phoneMap_['6'] = "mno";
        phoneMap_['7'] = "pqrs";
        phoneMap_['8'] = "tuv";
        phoneMap_['9'] = "wxyz";
    }

private:
    std::unordered_map<char, std::string> phoneMap_;

};