17-电话号码的字母组合

LeetCode 17. Letter Combinations of a Phone Number

LeetCode-17

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

method: 回溯

回溯三部曲：

1、确定回溯函数参数

对于给定的数字进行遍历，抓出每个数字对应的字符串，所以参数是给定的数字字符串digits和遍历的下标index

注意：是index在纵向遍历字符串digits，所以下一次递归的参数是index + 1
而i是在横向遍历每个数字对应的字母，每次都从0开始，与上一次递归无关

2、确定终止条件

当下标遍历完整个digits时返回，即index == digits.size()，或者path.size() == digits.size()

3、确定单层循环逻辑

对于每个数字对应的字符串，如index=0 -> digits[0] -> 2 -> letterMap[2] -> "abc"，要再进行遍历表示取或者不取，如可以取'a'，或者取'b'，或者取'c'

const string letterMap[10] = {
    "",
    "",
    "abc",
    "def",
    "ghi",
    "jkl",
    "mno",
    "pqrs",
    "tuv",
    "wxyz"
};  // 数字与字母对应关系

vector<string> res;
string path;
void traversal(const string& digits, int index) {
    if (index == digits.size()) {
        res.push_back(path);
        return;
    }
    int num = digits[index] - '0';   // 取出index对应的数字
    string letters = letterMap[num]; // 用数字拿到字母
    for (int i = 0; i < letters.size(); ++i) {
        path.push_back(letters[i]);
        dfs(digits, index + 1);     // 递归的是index+1
        path.pop_back();
    }
}
vector<string> letterCombinations(string digits) {
    if (digits.size() == 0) return res;
    reaversal(digits, 0);
    return res;
}