题目描述
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
网络异常，图片无法展示
|
示例:
输入："23" 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]. 复制代码
说明: 尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
DFS 回溯解法
对于字符串 ds 中的每一位数字，都有其对应的字母映射数组。
在 DFS 中决策每一位数字应该对应哪一个字母，当决策的位数 i == n，代表整个 ds
字符串都被决策完毕，将决策结果添加到结果集：
class Solution { Map<String, String[]> map = new HashMap<>(){{ put("2", new String[]{"a", "b", "c"}); put("3", new String[]{"d", "e", "f"}); put("4", new String[]{"g", "h", "i"}); put("5", new String[]{"j", "k", "l"}); put("6", new String[]{"m", "n", "o"}); put("7", new String[]{"p", "q", "r", "s"}); put("8", new String[]{"t", "u", "v"}); put("9", new String[]{"w", "x", "y", "z"}); }}; public List<String> letterCombinations(String ds) { int n = ds.length(); List<String> ans = new ArrayList<>(); if (n == 0) return ans; StringBuilder sb = new StringBuilder(); dfs(ds, 0, n, sb, ans); return ans; } void dfs(String ds, int i, int n, StringBuilder sb, List<String> ans) { if (i == n) { ans.add(sb.toString()); return; } String key = ds.substring(i, i + 1); String[] all = map.get(key); for (String item : all) { sb.append(item); dfs(ds, i + 1, n, sb, ans); sb.deleteCharAt(sb.length() - 1); } } } 复制代码
- 时间复杂度：
n代表字符串ds的长度，一个数字最多对应 4 个字符（7 对应 “pqrs"），即每个数字最多有 4 个字母需要被决策。复杂度为 O(4n)O(4 ^ n)O(4n) - 空间复杂度：有多少种方案，就需要多少空间来存放答案。复杂度为 O(4n)O(4 ^ n)O(4n)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.17 篇，系列开始于 2021/01/01，截止
于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
由于 LeetCode 的题目随着周赛 & 双周赛不断增加，为了方便我们统计进度，我们将按照系列起始时的总题数作为分母，完成的题目作为分子，进行进度计算。当前进度为 17/1916 。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：Github 地址 & Gitee 地址。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和一些其他的优选题解。
#算法与数据结构
#LeetCode题解
#算法面试
