题目

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
image.png
示例 1：

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

示例 2：

输入：digits = ""
输出：[]

示例 3：

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

提示：

  • 0 <= digits.length <= 4
  • digits[i] 是范围 ['2', '9'] 的一个数字。

    解题方法

    递归回溯

    通过递归回溯的方式穷举所有可能的组合。
    C++代码： ```cpp class Solution { private: const string letters[10] = {
      "",
  "",
  "abc",
  "def",
  "ghi",
  "jkl",
  "mno",
  "pqrs",
  "tuv",
  "wxyz"
    };

public: void backtracking(string& digits, int idx, vector& result, string& s) { if(idx==digits.size()) { result.push_back(s); return; } else { int digit = digits[idx]-‘0’; string letter = letters[digit]; for(int i=0; i<letter.size(); i++) { s.push_back(letter[i]); backtracking(digits, idx+1, result, s); s.pop_back(); } } }

vector<string> letterCombinations(string digits) {
    vector<string> result;
    string s = "";
    if(digits.size()) backtracking(digits, 0, result, s);

    return result;
}

};

隐藏回溯的写法如下
```cpp
class Solution {
private:
    const string letters[10] = {
        "",
        "",
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz"
    };

public:
    void backtracking(string& digits, int idx, vector<string>& result, const string& s) {            // 使用 const string&
        if(idx==digits.size()) {
            result.push_back(s);
            return;
        }
        else {
            int digit = digits[idx]-'0';
            string letter = letters[digit];
            for(int i=0; i<letter.size(); i++) backtracking(digits, idx+1, result, s+letter[i]);        // 隐藏回溯
        }
    }

    vector<string> letterCombinations(string digits) {
        vector<string> result;
        string s = "";
        if(digits.size()) backtracking(digits, 0, result, s);

        return result;
    }
};