1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution
{
public:
    std::vector<std::string> res;          // 存储结果集
    std::string path;                      // 当前路径
    std::vector<std::string> strs = {      // 数字对应的字母集
        "", "", "abc",
        "def", "ghi", "jkl",
        "mno", "pqrs", "tuv", "wxyz"
    };

    vector<string> letterCombinations(string digits)
    {
        if (digits.empty())                // 特殊情况处理：空字符串
            return res;
        dfs(digits, 0);                    // 从第一个数字开始递归
        return res;
    }

    void dfs(std::string& digits, int u)
    {
        if (u == digits.size())
        {
            res.push_back(path);           // 将当前路径加入结果集
            return;
        }
        for (char c : strs[digits[u] - '0']) // 遍历当前数字对应的字母集
        {
            path.push_back(c);             // 将当前字母加入路径
            dfs(digits, u + 1);            // 递归到下一个数字
            path.pop_back();               // 回溯，移除最后一个字母
        }
    }
};