LeetCode动画 | 17.电话号码的字母组合
LeetCode动画 | 17.电话号码的字母组合
今天分享一个LeetCode题，题号是17，题目是电话号码的字母组合，题目标签是字符串和回溯算法。
题目描述
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
电话号码的字母组合
示例:
输入："23" 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]. 说明: 尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
解题
此题涉及到回溯算法，回溯算法，顾名思义是一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现满足结束条件就“回溯”返回，寻找其它路径的选择。回溯算法伪代码框架如下：
回溯算法伪代码框架
// 回溯算法伪代码
res = [] // 动态数组，数组长度可变
方法函数track(多叉树或图，选择列表) {
if 满足结束条件 {
res.add(单源路径)
return;
}
for 选择节点 : 选择列表 {
选择节点；
track(多叉树或图，选择列表);
撤销选择节点;
}
}只要任何一个涉及到回溯算法的题，解决方法都包含这个代码框架，此题同样也是包含这个框架。
回到题目描述，输入示例“23”，“2”的选择列表有{“a”, “b”, “c”}，“3”的选择列表有{"d", "e", "f"}，生成多叉树，如下图：
输入23键
根节点为空，“2”的选择列表作为根节点的子节点，“3”的选择列表分别作为“2”的选择列表的子节点。要获取“2”和“3”两键的所有字母组合，将结束条件放在树的最底部。
此题中“23”是一个字符串，可以设置下标index从零开始。当下标为0时，获取的是“2”的选择列表；当下标为1时，获取的是“3”的选择列表；直到下标为2，组合字母之后则直接“回溯“到其它路径。结束条件代码如下：
if (index > digits.length() - 1) {
// Code
return;
}那如何作选择和撤销选择呢？看下图画出的方框：
画出的方框
在这个节点加上了类似机关的小方框，触发这个红色小方框则作选择，触发这个蓝色小方框则作撤销选择。选择是指将这个节点的值加入到某个组合中，撤销选择是指将这个节点的值从某组合中撤出。具体的程序执行动态看下面的算法动画视频，就能知道回溯算法是什么回事了，大家加油 8-)
动画：回溯算法
Code：使用回溯算法
// 创建直接寻址表
String[] digitsArr = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
List<String> res = new ArrayList<>(); // 动态数组
StringBuffer tmp = new StringBuffer();
public List<String> letterCombinations(String digits) {
if (digits == null || "".equals(digits)) return res;
track(digits, 0);
return res;
}
private void track(String digits, int index) {
if (index > digits.length() - 1) {
res.add(tmp.toString());
return;
}
String s = digitsArr[digits.charAt(index) - '0'];
for (int i = 0; i < s.length(); i++) {
tmp.append(s, i, i + 1);
track(digits, index + 1);
tmp.deleteCharAt(tmp.length() - 1);
}
}