来源：LeetCode 第17题【公众号：数据结构和算法】

给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。给出数字到字母的映射如下（与电话按键相同）。注意1不对应任何字母。

示例1：
输入：d i g i t s = " 2 3 " 
输出：[" a d "," a e "," a f"," b d "," b e "," b f"," cd "," ce "," c f"]示例2：
输入：d i g i t s = "" 
输出：[ ] 示例3：
输入：d i g i t s = " 2 " 
输出：[" a "," b "," c "] 

提示：

●  0<=digits.length<=4

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

解法一：BFS解决

每一个数字对应3到4个字符，我们以示例一为例画个图来看一下

我们看到实际上就是一颗n叉树，除了叶子节点外，每个节点都有3到4个子节点。对于二叉树的BFS遍历如下图所示，也就是一行一行的访问 。

二叉树的BFS遍历代码如下：

public void levelOrder(TreeNode tree) { //链表，这里我们可以把它看做队列 LinkedList 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 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 letterCombinations(String digits) { LinkedList 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，这里我们可以把它看做是一棵树的前序遍历。网上说这种是回溯算法，实际上这里往回走的时候并不需要撤销选择，因为字符串每次都会生成一个新的对象，所以并不会造成其他分支的污染;

public List letterCombinations(String digits) { List 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 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]); //因为字符串是创建了一个新的对象，所以这里不需要撤销 } 
}