17. 电话号码的字母组合
2022-08-02 本文已影响0人
水中的蓝天
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例.png
2对应abc 3对应def ... 9对应wxyz
分析:
其实就是给定一个数字组合的字符串，让我们转换成对应的所有字母组合排列；
有一个隐形条件就是虽然一个数字对应的是多个字母，但一次只能拿出一个字母来配对，就像电话按键输入一样
思路：
考虑使用DFS(Depth-first search 深度优先搜索)来解决此类问题，很多排列组合相关的问题，都可以通过DFS来解决
class Solution {
private char[] cs;//字符数组
private List<String> list;//最终存放字符组合的数组
//记录每一层选择的字母，一趟结束后再转成字符串就是一个字母组合咯
private char[] strings;
//数字字母对照表
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) {
//1.字符串为空 没有意义
if(digits == null) return null;
//1.1 定义一个最终存放字符组合的数组
list = new ArrayList<>();
//1.2 转字符数组
cs = digits.toCharArray();
//1.3 digits是空字符，直接返回 list
if(cs.length==0) return list;
//1.4 字母组合数组的长度和cs等长即可
strings = new char[cs.length];
//2. 搜索字母组合
dfs(0);
//3. 返回字符组合的数组
return list;
}
//私有 没有返回值 深度优先搜索
//idx: 正在搜索第idx层
private void dfs(int idx) {
//1.已经进入最后一层了 不能再深入 存起来得到的值
if(idx==cs.length) {
//得到一个正确的解，就添加到数组中
list.add(new String(strings));
return;
}
//数字字符
char digit = cs[idx];
//数字字符减去'2'就是对应索引 (2~0 3~1 4~2 ...) 就得到 所有能选择的字母
char[] letters = lettersArray[digit - '2'];
//2. 先枚举这一层可以做的所有选择
for(char letter : letters){
//取出其中一个字符记录下来
strings[idx] = letter;
//下一层 自动回溯
dfs(idx + 1);
}
}
}
