电话号码的字母组合

描述

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

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

示例 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’] 的一个数字。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/letter-combinations-of-a-phone-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

C++代码

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> res; // 存放结果的一维数组
        if(digits.empty()) return res; // 如果输入为空，直接返回空数组
        string path; // 存放当前组合的字符串
        vector<string> letter_map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; // 数字对应的字母表
        dfs(digits, 0, path, letter_map, res); // 开始回溯
        return res;
    }

    // digits: 输入的数字字符串，index: 当前处理的数字在数字字符串中的下标，path: 当前组合的字符串，letter_map: 数字对应的字母表，res: 存放结果的一维数组
    void dfs(string digits, int index, string& path, vector<string>& letter_map, vector<string>& res) {
        if(index == digits.size()) { // 如果当前处理的数字下标已经到达了数字字符串的末尾，说明找到了一个合法的组合
            res.push_back(path); // 将当前组合加入结果数组中
            return; // 回溯
        }
        string letters = letter_map[digits[index] - '0']; // 当前数字对应的字母表
        for(int i = 0; i < letters.size(); i++) { // 枚举可选的字母
            path.push_back(letters[i]); // 将当前字母加入当前组合
            dfs(digits, index + 1, path, letter_map, res); // 处理下一个数字，继续回溯
            path.pop_back(); // 回溯，将当前字母从当前组合中移除
        }
    }
};

这里使用了一个辅助函数 dfs 来进行回溯，其中 index 参数表示当前处理的数字在数字字符串中的下标。在每次递归中，我们枚举当前数字对应的可选字母表中的字母，将当前字母加入当前组合，继续回溯，最后将当前字母从当前组合中移除，回溯到上一层。当当前处理的数字下标已经到达了数字字符串的末尾时，说明找到了一个合法的组合，将其加入结果数组中。注意，在枚举可选的字母时，我们需要根据当前数字来获取对应的字母表，因此可以使用一个字符串数组 letter_map，将数字和对应的字母表一一对应起来。另外，如果输入的数字字符串为空，直接返回空数组。

Python代码

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        res = []
        path = ''
        letter_map = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']

        def dfs(index):
            nonlocal path
            if index == len(digits):
                res.append(path)
                return
            letters = letter_map[int(digits[index])]
            for letter in letters:
                path += letter
                dfs(index + 1)
                path = path[:-1]

        dfs(0)
        return res

与 C++ 版本的思路一致，使用递归函数 dfs 进行回溯，其中 index 参数表示当前处理的数字在数字字符串中的下标。在每次递归中，我们枚举当前数字对应的可选字母表中的字母，将当前字母加入当前组合，继续回溯，最后将当前字母从当前组合中移除，回溯到上一层。当当前处理的数字下标已经到达了数字字符串的末尾时，说明找到了一个合法的组合，将其加入结果数组中。注意，在枚举可选的字母时，我们需要根据当前数字来获取对应的字母表，因此可以使用一个字符串数组 letter_map，将数字和对应的字母表一一对应起来。另外，如果输入的数字字符串为空，直接返回空数组。