1.题目描述
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = ""
输出：[]
示例 3：
输入：digits = "2"
输出：["a","b","c"]
2.解题思路与代码
2.1 解题思路
这道题可以使用递归来完成，定义一个当前所指向数字的索引 index，然后根据这个索引 index 获取数字所对应的字母，使用一个 StringBuilder 存放这些字母，然后通过递归函数以继续处理往 index+1 操作，最后当 index 超过给定 digits 长度时表示当前这一组字母组合完毕，将 StringBuilder 内容放入结果数组中，然后返回。返回之后需要清除 StringBuilder 中当前加入的字母，即删除 StringBuilder 最后一个字母。
以 “23” 为例，首先我们从 2 开始，2 包含了字母 abc，因此在 2 这一级有 a、b、c 三个字母。首先我们从字母 a 开始，将字母 a 放入到 StringBuilder 中，然后继续往下处理到数字 3，数字 3 有 d、e、f 三个字母，那么首先将 d 追加到 StringBuilder 中，继续往 index+1 处理，此时 index 超过字符串长度，将 StringBuilder 中的 ad 放入结果列表中。
然后从 StringBuilder 中移除最后一位字母 d，返回到上一级继续向下处理，此时将字母 e 追加到 StringBuilder 中，此时 index+1 超过字符串长度，因此将字符串 ae 放入结果数组当中。之后继续重复上面的这一系列操作，便能够得到所有字母组合的结果列表。
2.2 代码
class Solution {
// 使用 Map 存放数字和数字对应字母数组的关系
private Map<Integer, char[]> map;
List<String> list = new ArrayList<>();
public Solution() {
map = new HashMap<>();
char[] two = {'a', 'b', 'c'};
char[] three = {'d', 'e', 'f'};
char[] four = {'g', 'h', 'i'};
char[] five = {'j', 'k', 'l'};
char[] six = {'m', 'n', 'o'};
char[] seven = {'p', 'q', 'r', 's'};
char[] eight = {'t', 'u', 'v'};
char[] nine = {'w', 'x', 'y', 'z'};
map.put(2, two);
map.put(3, three);
map.put(4, four);
map.put(5, five);
map.put(6, six);
map.put(7, seven);
map.put(8, eight);
map.put(9, nine);
}
public List<String> letterCombinations(String digits) {
if ("".equals(digits)){
return list;
}
process(0,digits,new StringBuilder());
return list;
}
public void process(int index, String digits, StringBuilder builder) {
if (index == digits.length()) {
list.add(builder.toString());
return;
}
int num = Integer.parseInt(String.valueOf(digits.charAt(index)));
char[] chars = map.get(num);
for (int i = 0; i < chars.length; i++) {
builder.append(chars[i]);
process(index + 1, digits, builder);
builder.delete(builder.length() - 1, builder.length());
}
}
}
2.3 测试结果
通过测试
3.总结
- 使用 Map 存放数字和字母列表的关系
- 使用递归组装字符串，并且在退出方法时需要删除 StringBuilder 中最后一个字母
