一、题目描述
来源：力扣（LeetCode）
给定一个仅包含数字 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); } } }
复杂度分析
时间复杂度：
网络异常，图片无法展示
|
m
是输入中对应
3
个字母的数字个数,
n
是输入中对应
4
个字母的数字个数
空间复杂度：
网络异常，图片无法展示
|
网络异常，图片无法展示
|
运行结果
网络异常，图片无法展示
|
总结
我们可以将问题模拟转为成我们相对比较熟悉的模型，这样能够帮助我们的更好的理解和更快的解决问题。
