【LeetCode每日一题】——17.电话号码的字母组合

一【题目类别】

• 回溯

二【题目难度】

• 中等

三【题目编号】

• 17.电话号码的字母组合

四【题目描述】

• 给定一个仅包含数字 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'] 的一个数字。

七【解题思路】

• 但凡涉及到组合类的题目，基本都使用回溯算法解决，本题也不例外，不过是在原本的基础上添加映射关系
• 根据题目信息可知，我们最终组合的是字母，但是输入数据为数字，所以需要简历一个数字到字母的映射
• 其余步骤和正常的回溯过程一致
  • 设置边界条件：如果所有的数字都遍历完毕了，就完成此次计算
  • 回溯拼接某一电话号码对应的字母：和正常的回溯过程一致，不过需要先取出数字对应的字母进行回溯
• 最后返回结果即可
• 具体细节可以参考下面的代码

八【时间频度】

• 时间复杂度：$O(3^m\times 4^n)$，$m$为$3$个字母对应的数字个数，$n$为$4$个字母对应的数字个数
• 空间复杂度：$O(m+n)$，$m$为$3$个字母对应的数字个数，$n$为$4$个字母对应的数字个数

九【代码实现】

1. Java语言版

class Solution {

    // 数字和字母的映射
    private static final String[] phoneMap = {
        "",
        "",
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz",
    };

    public List<String> letterCombinations(String digits) {
        // 边界条件的判断
        if (digits == null || digits.length() == 0) {
            return new ArrayList<>();
        }
        // 存储最终结果
        List<String> res = new ArrayList<>();
        // 从第一个电话号码开始计算
        dfs(res, new StringBuffer(), digits, 0);
        // 返回最终结算结果
        return res;
    }

    // 使用回溯计算电话号码的字母组合
    private void dfs(List<String> res, StringBuffer temp, String digits, int index) {
        // 将所有电话号码遍历完毕即可返回
        if (index == digits.length()) {
            res.add(temp.toString());
            return;
        }
        // 回溯拼接某一电话号码对应的字母
        char digit = digits.charAt(index);
        String letters = phoneMap[digit - '0'];
        
        for (int i = 0; i < letters.length(); i++) {
            temp.append(letters.charAt(i));
            dfs(res, temp, digits, index + 1);
            temp.deleteCharAt(temp.length() - 1);
        }
    }

}

2. Python语言版

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        # 边界条件的判断
        if not digits:
            return list()
        
        # 数字和字母的映射
        phoneMap = {
            "2" : "abc",
            "3" : "def",
            "4" : "ghi",
            "5" : "jkl",
            "6" : "mno",
            "7" : "pqrs",
            "8" : "tuv",
            "9" : "wxyz",
        }

        # 存储最终结果
        res = list()

        # 存储临时结果
        temp = list()

        # 使用回溯计算电话号码的字母组合
        def dfs(index):
            # 将所有电话号码遍历完毕即可返回
            if index == len(digits):
                res.append("".join(temp))
                return
            # 回溯拼接某一电话号码对应的字母
            digit = digits[index]
            for letter in phoneMap[digit]:
                temp.append(letter)
                dfs(index + 1)
                temp.pop()
        
        # 从第一个电话号码开始计算
        dfs(0)

        # 返回最终结算结果
        return res

3. C++语言版

class Solution {

public:

    // 数字和字母的映射
    const vector<string> phoneMap = {
        "",
        "",
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz",
    };

    // 使用回溯计算电话号码的字母组合
    void dfs(vector<string>& res, string& temp, string digits, int index) {
        // 将所有电话号码遍历完毕即可返回
        if (index == digits.size()) {
            res.push_back(temp);
            return;
        }
        // 回溯拼接某一电话号码对应的字母
        int digit = digits[index] - '0';
        const string& letters = phoneMap[digit];
        for (char letter : letters) {
            temp.push_back(letter);
            dfs(res, temp, digits, index + 1);
            temp.pop_back();
        }
    }

    vector<string> letterCombinations(string digits) {
        // 存储最终结果
        vector<string> res;
        // 边界条件的判断
        if (digits.empty()) {
            return res;
        }
        // 存储临时结果
        string temp;
        // 从第一个电话号码开始计算
        dfs(res, temp, digits, 0);
        // 返回最终结算结果
        return res;
    }
};

十【提交结果】

1. Java语言版
   

2. Python语言版
   

3. C++语言版