leetcode|中等:17. 电话号码的字母组合

1.题目

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

2. 题解

2.1 思路分析

思路1：DFS 比较简单 直接看代码

2.2 代码实现

class Solution {
    public void dfs(char[] tel,int depth,HashMap<Character,String> digit2CharsMap,String digits,List<String> res){
        // dfs出口
        if(depth==tel.length) {
            res.add(new String(tel));
            return;
        }

        char curDigit = digits.charAt(depth);
        char[] digit2Chars = digit2CharsMap.get(curDigit).toCharArray();

        for(int i=0;i<digit2Chars.length;i++){
            tel[depth]=digit2Chars[i];
            dfs(tel,depth+1,digit2CharsMap,digits,res);
        }
    }


    public List<String> letterCombinations(String digits) {

        HashMap<Character,String> digit2CharsMap = new HashMap<>();
        digit2CharsMap.put('2',"abc");
        digit2CharsMap.put('3',"def");
        digit2CharsMap.put('4',"ghi");
        digit2CharsMap.put('5',"jkl");
        digit2CharsMap.put('6',"mno");
        digit2CharsMap.put('7',"pqrs");
        digit2CharsMap.put('8',"tuv");
        digit2CharsMap.put('9',"wxyz");

        List<String> res = new ArrayList<>();
        if(digits.length()==0){
            return res;
        }
        char[] tel = new char[digits.length()];

        dfs(tel,0,digit2CharsMap,digits,res);
        return res;
    }
}

2.3 提交结果

参考资料

1. https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/