630，Leetcode原题电话号码的字母组合的两种解法，你会么？
问题描述
来源：LeetCode第17题
难度：中等
给定一个仅包含数字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']的一个数字。
BFS解决
每一个数字对应3到4个字符，我们以示例一为例画个图来看一下
我们看到实际上就是一颗n叉树，除了叶子节点外，每个节点都有3到4个子节点。对于二叉树的BFS遍历如下图所示，也就是一行一行的访问
二叉树的BFS遍历代码如下
public void levelOrder(TreeNode tree) {
//链表，这里我们可以把它看做队列
LinkedList<TreeNode> list = new LinkedList<>();
list.add(tree);//相当于把数据加入到队列尾部
while (!list.isEmpty()) {
//poll方法相当于移除队列头部的元素
TreeNode node = list.poll();
//访问当前节点
System.out.println(node.val);
//遍历当前节点的左子节点和右子节点
if (node.left != null)
list.add(node.left);
if (node.right != null)
list.add(node.right);
}
}
因为最多有两个子节点所以是二叉树，如果最多有n个子节点我们可以称它为n叉树，那么n叉树的子节点比较多，我们不可能一次性全部写完，可以使用for循环来遍历，代码如下
public void levelOrder(TreeNode tree) {
//链表，这里我们可以把它看做队列
LinkedList<TreeNode> list = new LinkedList<>();
list.add(tree);//相当于把数据加入到队列尾部
while (!list.isEmpty()) {
//poll方法相当于移除队列头部的元素
TreeNode node = list.poll();
//访问当前节点
System.out.println(node.val);
//遍历当前节点的所有子节点
for (int i = 0; i < node.child.count; i++) {
list.add(node.child[i]);
}
}
}
搞懂了上面的代码，那么这题的答案就比较简单了。实际上这题给的并不是一棵树，这棵树只是我们想象的，那我们怎么确定走到叶子节点了呢，实际上很简单，如果有n个数字，那么叶子节点字符串的长度就应该是n。来看下代码
//BFS
public List<String> letterCombinations(String digits) {
LinkedList<String> res = new LinkedList<>();
//空判断
if (digits == null || digits.isEmpty())
return res;
char[][] tab = {{'a', 'b', 'c'}, {'d', 'e', 'f'}, {'g', 'h', 'i'},
{'j', 'k', 'l'}, {'m', 'n', 'o'}, {'p', 'q', 'r', 's'},
{'t', 'u', 'v'}, {'w', 'x', 'y', 'z'}};
res.add("");
while (res.peek().length() != digits.length()) {
String remove = res.poll();//出队
char[] chars = tab[digits.charAt(remove.length()) - '2'];
//相当于当前节点的所有子节点
for (int i = 0; i < chars.length; i++) {
res.add(remove + chars[i]);//入队
}
}
return res;
}DFS解决
对于一棵树的遍历，除了BFS以外我们很自然的会想到DFS，这里我们可以把它看做是一棵树的前序遍历。网上说这种是回溯算法，实际上这里往回走的时候并不需要撤销选择，因为字符串每次都会生成一个新的对象，所以并不会造成其他分支的污染，关于回溯算法具体可以看下450，什么叫回溯算法，一看就会，一写就废。我们来看下这题的代码
public List<String> letterCombinations(String digits) {
List<String> res = new ArrayList<>();
if (digits == null || digits.isEmpty())
return res;
char[][] tab = {{'a', 'b', 'c'}, {'d', 'e', 'f'}, {'g', 'h', 'i'},
{'j', 'k', 'l'}, {'m', 'n', 'o'}, {'p', 'q', 'r', 's'},
{'t', 'u', 'v'}, {'w', 'x', 'y', 'z'}};
dfs(res, 0, digits, tab, "");
return res;
}
/**
* @param res
* @param index 表示访问到第几个数字了，也可以认为访问到树的第几层了
* @param digits
* @param tab
* @param path 从根节点到叶子结点的路径
*/
private void dfs(List<String> res, int index, String digits, char[][] tab, String path) {
//到叶子节点了，就把这条路径选择的字符添加到res中
if (path.length() == digits.length()) {
res.add(path);
return;
}
char[] chars = tab[digits.charAt(index) - '2'];
//访问当前节点的所有子节点
for (int i = 0; i < chars.length; i++) {
dfs(res, index + 1, digits, tab, path + chars[i]);
//因为字符串是创建了一个新的对象，所以这里不需要撤销
}
}
截止到目前我已经写了600多道算法题了，为了方便大家阅读，我把部分算法题整理成了pdf文档，目前有1000多页，大家可以在下面公众号“数据结构和算法”中回复关键字“pdf”即可获取下载链接。
想学习算法，还可以长按下面二维码加我微信，我给你拉到算法学习群，在工作中或者学习中遇到不会的问题都可以在群里讨论。