LeetCode刷题Java版：017.电话号码的字母组合
作者：沉默王二
发布时间：2022-08-03T17:00:01.017+0800
017.电话号码的字母组合
题意
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
难度
中等
示例
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
分析
实际上，题目就是要我们找出数字对应的字符的所有可能。
每个字符对应一种可能，就形成了一颗类似于树的结构，将第一位的所有可能指向一个空结点，那么它就是一颗真实存在的树的结构，一般称它为解答树（示例如下），只需要遍历这棵树，并且输出根节点到叶子节点的路径，就能找到答案了。
digits = "23" root
/ \
2对应的字符 'a' 'b'
/ | \ / | \
3对应的字符 'd' 'e' 'f' 'd' 'e' 'f'
说白了，就是把根节点到叶子节点的每一条路径上的所有字符加起来，就是答案。
所以我们现在的问题是把这颗树建立起来，然后对它进行深度优先遍历（dfs）。实际上，我们并不需要将建树和遍历这两个操作分开，因为建树的时候就需要按照深度优先遍历的顺序去创建它。
public class Solution {
private final String[] letterMap = {
" ", //0
"", //1
"abc", //2
"def", //3
"ghi", //4
"jkl", //5
"mno", //6
"pqrs", //7
"tuv", //8
"wxyz" //9
};
List
String message;
String str;
private void dfs(int step){
if(step == message.length()){
ans.add(str);
return ;
}
String temp = str;
if(message.charAt(step) == '1')//'1'的话直接跳过
dfs(step + 1);
else
for(int i = 0;i < letterMap[message.charAt(step) - '0'].length();i++){
str = temp;
str = str + letterMap[message.charAt(step) - '0'].charAt(i);
dfs(step + 1);//进入下一层
}
}
public List
if(digits.length() == 0)
return ans;
str = "";
message = digits;
dfs(0);
return ans;
}
}
总结
这次，我们接触了“解答树”（之所以叫解答树，是因为答案就在这颗树上面，深度优先遍历后就是答案，竞赛中常见的名词），并且通过建树和深度优先遍历得出答案。
当题目要求我们列出所有可能的时候，解答树显然就是一个不错的选择，直观而可靠。
力扣链接：https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
017.电话号码的字母组合
题意
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
难度
中等
示例
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
分析
实际上，题目就是要我们找出数字对应的字符的所有可能。
每个字符对应一种可能，就形成了一颗类似于树的结构，将第一位的所有可能指向一个空结点，那么它就是一颗真实存在的树的结构，一般称它为解答树（示例如下），只需要遍历这棵树，并且输出根节点到叶子节点的路径，就能找到答案了。
digits = "23" root
/ \
2对应的字符 'a' 'b'
/ | \ / | \
3对应的字符 'd' 'e' 'f' 'd' 'e' 'f'
说白了，就是把根节点到叶子节点的每一条路径上的所有字符加起来，就是答案。
所以我们现在的问题是把这颗树建立起来，然后对它进行深度优先遍历（dfs）。实际上，我们并不需要将建树和遍历这两个操作分开，因为建树的时候就需要按照深度优先遍历的顺序去创建它。
public class Solution {
private final String[] letterMap = {
" ", //0
"", //1
"abc", //2
"def", //3
"ghi", //4
"jkl", //5
"mno", //6
"pqrs", //7
"tuv", //8
"wxyz" //9
};
List
String message;
String str;
private void dfs(int step){
if(step == message.length()){
ans.add(str);
return ;
}
String temp = str;
if(message.charAt(step) == '1')//'1'的话直接跳过
dfs(step + 1);
else
for(int i = 0;i < letterMap[message.charAt(step) - '0'].length();i++){
str = temp;
str = str + letterMap[message.charAt(step) - '0'].charAt(i);
dfs(step + 1);//进入下一层
}
}
public List
if(digits.length() == 0)
return ans;
str = "";
message = digits;
dfs(0);
return ans;
}
}
总结
这次，我们接触了“解答树”（之所以叫解答树，是因为答案就在这颗树上面，深度优先遍历后就是答案，竞赛中常见的名词），并且通过建树和深度优先遍历得出答案。
当题目要求我们列出所有可能的时候，解答树显然就是一个不错的选择，直观而可靠。
力扣链接：https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
017.电话号码的字母组合
题意
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
难度
中等
示例
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
分析
实际上，题目就是要我们找出数字对应的字符的所有可能。
每个字符对应一种可能，就形成了一颗类似于树的结构，将第一位的所有可能指向一个空结点，那么它就是一颗真实存在的树的结构，一般称它为解答树（示例如下），只需要遍历这棵树，并且输出根节点到叶子节点的路径，就能找到答案了。
digits = "23" root
/ \
2对应的字符 'a' 'b'
/ | \ / | \
3对应的字符 'd' 'e' 'f' 'd' 'e' 'f'
说白了，就是把根节点到叶子节点的每一条路径上的所有字符加起来，就是答案。
所以我们现在的问题是把这颗树建立起来，然后对它进行深度优先遍历（dfs）。实际上，我们并不需要将建树和遍历这两个操作分开，因为建树的时候就需要按照深度优先遍历的顺序去创建它。
public class Solution {
private final String[] letterMap = {
" ", //0
"", //1
"abc", //2
"def", //3
"ghi", //4
"jkl", //5
"mno", //6
"pqrs", //7
"tuv", //8
"wxyz" //9
};
List
String message;
String str;
private void dfs(int step){
if(step == message.length()){
ans.add(str);
return ;
}
String temp = str;
if(message.charAt(step) == '1')//'1'的话直接跳过
dfs(step + 1);
else
for(int i = 0;i < letterMap[message.charAt(step) - '0'].length();i++){
str = temp;
str = str + letterMap[message.charAt(step) - '0'].charAt(i);
dfs(step + 1);//进入下一层
}
}
public List
if(digits.length() == 0)
return ans;
str = "";
message = digits;
dfs(0);
return ans;
}
}
总结
这次，我们接触了“解答树”（之所以叫解答树，是因为答案就在这颗树上面，深度优先遍历后就是答案，竞赛中常见的名词），并且通过建树和深度优先遍历得出答案。
当题目要求我们列出所有可能的时候，解答树显然就是一个不错的选择，直观而可靠。
力扣链接：https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
知识星球
扫码加入星球
查看更多优质内容
https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412