17.电话号码的字母组合
#回溯 2024-08-09 
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
class Solution {
public:
    const string list[10] = {"",    "",    "abc",  "def", "ghi",
                             "jkl", "mno", "pqrs", "tuv", "wxyz"};

    vector<string> result;
    string path;
    void backtrace(string digits, int size, int note, int start) {
        if (note == size) {
            result.push_back(path);
            return;
        }
        for (int i = start; i < size; i++) {
            int num = digits[i] - '0';
            for (int j = 0; j < list[num].size(); j++) {
                path.push_back(list[num][j]);
                note++;
                backtrace(digits, size, note, i + 1);
                path.pop_back();
                note--;
            }
        }
    }

    vector<string> letterCombinations(string digits) {
        if (!digits.empty()) {
            backtrace(digits, digits.size(), 0, 0);
        }
        return result;
    }
};

在完成《77.组合》基础上，这道题你要会两个技能，分别是建立映射关系（通常是数组）和单个数字字符转换为对应的整数（ch - ‘0’）。