https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/

方法1

可能是占用内存最小的方法，但解法不够通用

class Solution {
public:
    Solution() {
        for (auto it: map_digit_chars) {
            num_digits[it.first] = it.second.length();
        }
    }
    vector<string> letterCombinations(string digits) {
        if (digits.empty())  return vector<string>();
        int num_combinations = 1;
        for (const char c: digits) {
            num_combinations *= num_digits[c];
        }
        vector<string> ret_val = vector<string>(num_combinations, string(digits.length(), '0'));
        int last_level_factor = 1;
        for (int i = digits.length() - 1; i >= 0 ; --i) {
            for (int j = 0, char_index = 0; j < num_combinations; 
            char_index = (++char_index) % (num_digits[digits[i]])) {
                // 填第i位字母的小循环
                for (int k = 0; k < last_level_factor; ++k) {
                    ret_val[j++][i] = map_digit_chars[digits[i]][char_index];
                }
            }
            last_level_factor *= num_digits[digits[i]];
        }
        return ret_val;
    }

   
private:
    unordered_map<char, int> num_digits;
    unordered_map<char, string> map_digit_chars {
        {'2', "abc"},
        {'3', "def"},
        {'4', "ghi"},
        {'5', "jkl"},
        {'6', "mno"},
        {'7', "pqrs"},
        {'8', "tuv"},
        {'9', "wxyz"}
    };
};

解法2

使用标准的回溯思想

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty())  return vector<string>();
        helper("", digits);
        return res;
    }

    void helper(string tmp_res, const string& digits) {
        if (tmp_res.length() == digits.length()) {
            res.push_back(tmp_res);
            return;
        }
        for (char c: map_digit_chars[digits[tmp_res.length()]]) {
            tmp_res.push_back(c);
            helper(tmp_res, digits);
            tmp_res.pop_back();
        }
    }

   
private:
    vector<string> res;
    unordered_map<int, string> map_digit_chars {
        {'2', "abc"},
        {'3', "def"},
        {'4', "ghi"},
        {'5', "jkl"},
        {'6', "mno"},
        {'7', "pqrs"},
        {'8', "tuv"},
        {'9', "wxyz"}
    };
};

关于回溯，本质上是DFS，可以参考：https://segmentfault.com/a/1190000006121957
其中最有用的是一个模板：

boolean solve(Node n) {
    if n is a leaf node {
        if the leaf is a goal node, return true
        else return false
    } else {
        for each child c of n {
            if solve(c) succeeds, return true
        }
        return false
    }
}