当前位置：网站首页>【刷题记录】17. 电话号码的字母组合

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

2022-07-21 21:43:00 【InfoQ】

一、题目描述

来源：

力扣（LeetCode）

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = &quot;23&quot;
输出：[&quot;ad&quot;,&quot;ae&quot;,&quot;af&quot;,&quot;bd&quot;,&quot;be&quot;,&quot;bf&quot;,&quot;cd&quot;,&quot;ce&quot;,&quot;cf&quot;]

示例 2：

输入：digits = &quot;&quot;
输出：[]

示例 3：

输入：digits = &quot;2&quot;
输出：[&quot;a&quot;,&quot;b&quot;,&quot;c&quot;]

提示：

0 <= digits.length <= 4

digits[i] 是范围 ['2', '9'] 的一个数字。

二、思路分析

hashMap + DFS 深度优先搜索

从题目中可以看出，每一个数字都对应字符数组。我们用可以
map
来存这个对应的关系

其实每一个数字我们都可以看成一个树的节点，而对应的字符，就可以看作是这个节点下的分支

每多一个数字，就相当于在分支的节点下多一个相应的情况分支。

然后我们对这个树进行遍历即为我们想要的最终结果例如上面的示例 1：

代码实现

class Solution1 {
 Map<Character, String> map = new HashMap<Character, String>() {{
 put('2', &quot;abc&quot;);
 put('3', &quot;def&quot;);
 put('4', &quot;ghi&quot;);
 put('5', &quot;jkl&quot;);
 put('6', &quot;mno&quot;);
 put('7', &quot;pqrs&quot;);
 put('8', &quot;tuv&quot;);
 put('9', &quot;wxyz&quot;);
 }};

 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);
 }
 }
}