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

2022 年 7 月 21 日
本文字数：1022 字
阅读完需：约 3 分钟

一、题目描述

给定一个仅包含数字 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);        }    }}

复制代码

复杂度分析

时间复杂度： $O (3^{M} \times 4^{N})$ ，其中 m 是输入中对应 3 个字母的数字个数, n 是输入中对应 4个字母的数字个数

空间复杂度： $O (3^{M} \times 4^{N})$ 。一共要生成 $3^{M} \times 4^{N}$ 个结果

运行结果

总结

我们可以将问题模拟转为成我们相对比较熟悉的模型，这样能够帮助我们的更好的理解和更快的解决问题。

发布于: 刚刚阅读数: 5

原文链接:【http://xie.infoq.cn/article/7ec62ec9a9c39cff9a41d64be】。

WangNing

关注

还未添加个人签名 2020.10.13 加入

一个只想提(快)升(乐)自(摸)我(鱼)的混子选手～

发布

暂无评论

创作场景

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

一、题目描述

二、思路分析

代码实现

复杂度分析

运行结果

总结

WangNing

评论