LeetCode 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'] 的一个数字。

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 微信：278166530
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 电话号码的字母组合（LeetCode 17）：https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
class Solution {
    // 映射表
    Map<Character, String> phoneMap;

    // 结果
    List<String> ans;

    // 把 digits 作为全局变量使用方便
    String digits;

    public List<String> letterCombinations(String digits) {

        // 赋值
        this.digits = digits;

        // 初始化
        ans = new ArrayList<String>();
        
        // 边界处理
        if (digits.length() == 0) {
            return ans;
        }

        // 建立映射关系
        phoneMap = new HashMap<Character, String>() {{
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }};

        // 使用深度优先搜索
        dfs( 0, "");

        // 返回结果
        return ans;
    }

    // 搜索框架
    // 在整个搜索过程中，变化的是当前这个数字，比如 2 、3 、4
    // index：当前访问 digits 上的字符索引为多少
    // str：已经拼接的字符串
    public void dfs(int index, String str) {

        // 递归的终止条件
        // 当访问完了每个位置的字符时，已经获取到一个完整的字符串了
        if (index == digits.length()) {

            // 记录结果
            ans.add(str);
            return;

        }

        // 获取 index 位置的字符
        // 假设输入的字符是"234"
        // 第一次递归时 index 为 0 ，digit 为 2 
        // 第二次递归时 index 为 1 ，digit 为 3 
        // 第三次递归时 index 为 2 ，digit 为 4
        char digit = digits.charAt(index);

        // 通过 digit 这个 key 查找出哈希表 phoneMap 中对应的 value
        // 比如  digit 为 2 ，那么 letters 就是 abc
        String letters = phoneMap.get(digit);

        // 获取 letters 的长度
        int lettersCount = letters.length();

        // 访问 letters 中的每个字符
        for (int i = 0; i < lettersCount; i++) {
            
            // 调用下一层递归
            // 不断的把结果累加到 str 上
            dfs( index + 1, str + letters.charAt(i));

        }
    }
}

**2、**C++ 代码

3、Python 代码

# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 微信：278166530
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 电话号码的字母组合（LeetCode 17）：https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        # 初始化
        ans = []
        
        # 边界处理
        if len(digits) == 0 :
            return ans
        

        # 建立映射关系
        phoneMap = {
            "2":"abc",
            "3":"def",
            "4":"ghi",
            "5":"jkl",
            "6":"mno",
            "7":"pqrs",
            "8":"tuv",
            "9":"wxyz"
        }
        # 搜索框架
        # 在整个搜索过程中，变化的是当前这个数字，比如 2 、3 、4
        # index：当前访问 digits 上的字符索引为多少
        # str：已经拼接的字符串
        def dfs(index, str):   

            # 递归的终止条件
            # 当访问完了每个位置的字符时，已经获取到一个完整的字符串了
            if index == len(digits) :

                # 记录结果
                ans.append(str)
                return

        

            # 获取 index 位置的字符
            # 假设输入的字符是"234"
            # 第一次递归时 index 为 0 ，digit 为 2 
            # 第二次递归时 index 为 1 ，digit 为 3 
            # 第三次递归时 index 为 2 ，digit 为 4
            digit = digits[index]

            # 通过 digit 这个 key 查找出哈希表 phoneMap 中对应的 value
            # 比如  digit 为 2 ，那么 letters 就是 abc
            letters = phoneMap[digit]

            # 访问 letters 中的每个字符
            for i in letters:  
            
                # 调用下一层递归
                # 不断的把结果累加到 str 上
                dfs( index + 1, str + i)

        # 使用深度优先搜索
        dfs(0 , "")

        # 返回结果
        return ans