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

力扣题目链接

给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。给出数字到字母的映射如下（与电话按键相同）：

示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：
输入：digits = ""
输出：[]

示例 3：
输入：digits = "2"
输出：["a","b","c"]

回溯法，时间复杂度与空间复杂度均取决于输入字符串的长度：

#include 
#include 

using namespace std;

class Solution {
private:
    const string letter_map[8] = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    vector result; // 结果集 由数个字符串结果项组成
    string s; // 表征每一个结果项

public:
    void backtracking(const string &digits, int index) {
        if (index == digits.size()) {
            result.push_back(s); // 向结果集result追加结果项s
            return;
        }

        string letters = letter_map[digits[index] - '2']; // 本层所有需要处理的letter的集合

        for (char letter : letters) { // 依次处理每个letter
            s.push_back(letter); // 向结果项s追加letter
            backtracking(digits, index + 1); // 向下递归 继续追加后续letter
            s.pop_back(); // 向上回溯 撤销当前letter
        }
    }

    vector letterCombinations(const string &digits) {
        s.clear();
        result.clear();
        if (digits.empty()) {
            return result;
        }
        backtracking(digits, 0);
        return result;
    }
};

int main() {
    Solution solution;

    for (const auto &i : solution.letterCombinations(string("23"))) {
        cout << i << " ";
    }
    return 0;
}