【刷题记录】17. 电话号码的字母组合-一一网

Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

一、题目描述

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

二、思路分析

hashMap + DFS 深度优先搜索

从题目中可以看出，每一个数字都对应字符数组。我们用可以map来存这个对应的关系
其实每一个数字我们都可以看成一个树的节点，而对应的字符，就可以看作是这个节点下的分支
每多一个数字，就相当于在分支的节点下多一个相应的情况分支。
然后我们对这个树进行遍历即为我们想要的最终结果

例如上面的示例 1：

代码实现

class Solution1 {
    Map<Character, String> map = 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");
    }};

    public List<String> letterCombinations(String ds) {
        int length = ds.length();

        List<String> res = new ArrayList<>();
        if (length == 0) return res;

        StringBuilder sb = new StringBuilder();
        dfs(ds, 0, length, sb, res);
        return res;
    }

    void dfs(String ds, int i, int n, StringBuilder sb, List<String> res) {
        if (i == n) {
            res.add(sb.toString());
            return;
        }

        char key = ds.charAt(i);

        String letters = map.get(key);
        for (int j = 0; j < letters.length(); j++){
            sb.append(letters.charAt(j));
            dfs(ds, i +1 , n, sb, res);
            sb.deleteCharAt(sb.length() -1);
        }
    }
}
复制代码