题目

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

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

img

示例 1：

输入：digits = "23"
输出：["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'] 的一个数字。

解答

  • 回溯法

理解本题后，要解决如下三个问题：

  1. 数字和字母如何映射？使用二维数组即可。
  2. 两个字母就两个for循环，三个字符我就三个for循环，以此类推，然后发现代码根本写不出来，此时的思路就是使用增加了遍历深度的参数的辅助函数进行辅助，得到一种符合要求的结果后进行回溯继续遍历。
  3. 输入1 * #按键等等异常情况（异常情况在leetcode样例中不存在，所以不考虑也没关系）

C++代码如下：

class Solution {
private:
    // 字母和数字的映射
    const string letterMap[10] = {
        "", // 0
        "", // 1
        "abc", // 2
        "def", // 3
        "ghi", // 4
        "jkl", // 5
        "mno", // 6
        "pqrs", // 7
        "tuv", // 8
        "wxyz", // 9
    };
public:
    vector<string> result; // 用于存储最终结果的全局变量动态数组result
    string s; // 用于临时存储一个组合的字符串s
    void backtracking(const string& digits, int index) {
        // 辅助函数，增加了一个index用于辅助遍历的过程，index表示遍历到digits的第几位
        if (index == digits.size()) {
            // 判断index是否和digits的大小相等，如果相等则说明当前已经遍历完了最后一位
            result.push_back(s); // 此时直接把保存的字符串s放进结果数组result中即可
            return; // 遍历结束直接return
        }
        int digit = digits[index] - '0'; // 把字符串中的单个数字转为int类型
        string letters = letterMap[digit]; // 通过获得的int类型数字得到对应的字符串映射
        for (int i = 0; i < letters.size(); i++) {
            s.push_back(letters[i]); // 将第i个字母进行push
            backtracking(digits, index + 1); // 递归进一步遍历
            s.pop_back(); // 回溯
        }

    }
    vector<string> letterCombinations(string digits) {
        s.clear(); // 初始化参数
        result.clear(); // 初始化参数
        if (digits.size() == 0) return result; // 如果digits数组的长度为0 直接返回空结果数组
        backtracking(digits, 0); // 递归调用，从0开始遍历
        return result; // 返回最终的结果数组
    }
};