Version: Next
17.电话号码的字母组合
难度 中等
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = ""
输出：[]
示例 3：
输入：digits = "2"
输出：["a","b","c"]
提示：
0 <= digits.length <= 4digits[i]是范围['2', '9']的一个数字。
DFS
- 自顶向下，画图
- 深度优先，先找出一个答案，层数越界的时候就是更新答案的时机
- 没有更深的下一层了，就
回溯
public class _17电话号码的字母组合 {
// 数字字母映射数组
private char[][] lettersArray = {
{'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'}
};
private char[] chars; // 把输入数字字符串切分为字符数组
private List<String> resultList;
private char[] singleResult; // 存储单个组合，用于之后再转成字符串添加到 List 中
public List<String> letterCombinations(String digits) {
chars = digits.toCharArray();
resultList = new ArrayList<>();
singleResult = new char[chars.length];
if (chars.length == 0) return resultList;
// DFS
dfs(0);
return resultList;
}
/**
* 深度优先索索
*
* @param depth 正在搜索的层深度
*/
private void dfs(int depth) {
if (depth == chars.length) { // 深度越界了
// 找到了一个解，把单个组合转换成一个字符串，存到总结果集里
resultList.add(new String(singleResult));
return;
}
// 获取当前层是哪一个数字
char digit = chars[depth];
// 获取数字对应的可选字母
char[] letters = lettersArray[digit - '2'];
// 枚举当前层可用的所有字母
for (char l : letters) {
singleResult[depth] = l; // 把被选中的那个字母放到单词字符数组中，等待转成字符串
dfs(depth + 1);
}
}
}
将成员变量更换为方法参数
一般写 DFS 不会设置上述写法中的成员变量
- 那么就要在方法调用时，不断的传递这些对象
public class _17电话号码的字母组合_无成员 {
// 数字字母映射数组
private char[][] lettersArray = {
{'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'}
};
public List<String> letterCombinations(String digits) {
char[] chars = digits.toCharArray();
List<String> resultList = new ArrayList<>();
char[] singleResult = new char[chars.length];
if (chars.length == 0) return resultList;
// DFS
dfs(0, chars, singleResult, resultList);
return resultList;
}
/**
* 深度优先索索
*
* @param depth 正在搜索的层深度
*/
private void dfs(int depth, char[] chars, char[] singleResult, List<String> resultList) {
if (depth == chars.length) { // 深度越界了
// 找到了一个解，把单个组合转换成一个字符串，存到总结果集里
resultList.add(new String(singleResult));
return;
}
// 获取当前层是哪一个数字
char digit = chars[depth];
// 获取数字对应的可选字母
char[] letters = lettersArray[digit - '2'];
// 枚举当前层可用的所有字母
for (char l : letters) {
singleResult[depth] = l; // 把被选中的那个字母放到单词字符数组中，等待转成字符串
dfs(depth + 1, chars, singleResult, resultList);
}
}
}
DFS 的套路
- 首先确定进入哪一层
- 确定不能再去更深层搜索的退出条件
- 写正常搜索时如何操作
- 枚举当前层可以做的选择
- 枚举到一个值，将这个值暂时存储，用于后续组合成一个完整的单个解
- 去下一层
- 达到最底，回溯