Leetcode 17.电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例:
- 输入："23"
- 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明：尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
解题思路：
结束条件：
输入用例"23"，两个数字，我们收集的["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].这些正好每个子集是两位，如果是"234"，["adg","adh","adi","aeg","aeh","aei","afg","afh","afi","bdg","bdh","bdi","beg","beh","bei","bfg","bfh","bfi","cdg","cdh","cdi","ceg","ceh","cei","cfg","cfh","cfi"]，发现了吗？每个子集都是三位，也就是说我们的结束条件可以设置为：
if (digits.length() == index) {
// 如果已经遍历完所有数字，则将当前的组合添加到结果列表中
res.add(sb.toString());
// 返回上一层递归
return;
}
总感觉这里有找规律的嫌疑。。
具体步骤：
- 首先，我们需要建立一个映射关系，将数字与对应的字母组合关联起来。可以使用一个字符串数组
letters来表示，其中每个下标对应一个数字，而对应的字符串则是该数字对应的字母组合。例如，letters[2]表示数字2对应的字母组合是"abc"，letters[3]表示数字3对应的字母组合是"def"，以此类推。 - 接下来，我们定义一个空的结果列表
res用于存储生成的所有字母组合。我们还定义一个StringBuilder对象sb用于构建组合。 - 首先，我们进行一些基础的检查，如果
digits为空或长度为0，那么直接返回空列表res。 - 然后，我们调用
backTracking方法开始回溯算法。该方法接受两个参数：digits和index。digits是输入的数字字符串，index是当前处理的数字的索引。开始时，将index设为0。 - 在
backTracking方法中，我们首先检查当前的index是否等于digits的长度。如果相等，说明我们已经遍历完了所有的数字，此时将sb的内容转换为字符串，并将它添加到结果列表res中。然后，返回上一层递归。 - 如果
index不等于digits的长度，说明我们还没有处理完所有的数字。我们通过digits.charAt(index)获取当前数字，并将其转换为对应的整数digit。 - 接下来，我们获取
digit对应的字母组合字符串str，从letters数组中根据digit的值取出对应的字符串。 - 然后，我们遍历
str中的每个字符。对于每个字符，我们将其添加到sb中，表示我们选取了该字符作为当前数字的字母组合之一。 - 然后，我们递归调用
backTracking方法，传入digits和index + 1，即处理下一个数字的字母组合。 - 在递归调用返回后，表示已经完成了对下一个数字的处理，我们需要进行回溯。回溯的操作是删除
sb中的最后一个字符，以便尝试下一个字符作为当前数字的字母组合。 - 最后，当所有的数字都处理完毕后，回溯算法结束，我们将得到的所有字母组合存储在
res中，并将其作为结果返回。
下面举个例子说一下：输入digits："23"
我已经用黄色的笔画出递归+for循环的执行顺序，大家可以参考~
代码实现：
class Solution {
// 存储结果组合的列表
List<String> res = new ArrayList();
// 数字与对应字母的映射数组
String[] letters = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
// 用于构建组合的字符串
StringBuilder sb = new StringBuilder();
public List<String> letterCombinations(String digits) {
if (digits == null || digits.length() == 0) {
// 如果输入的数字为空或长度为0，则返回空列表
return new ArrayList();
}
// 进行回溯算法生成组合
backTracking(digits, 0);
// 返回结果列表
return res;
}
public void backTracking(String digits, int index) {
if (digits.length() == index) {
// 如果已经遍历完所有数字，则将当前的组合添加到结果列表中
res.add(sb.toString());
// 返回上一层递归
return;
}
// 获取digits中的当前数字
int digit = digits.charAt(index) - '0';
// 获取数字对应的字母表
String str = letters[digit];
for (int i = 0; i < str.length(); i++) {
// 将当前字母添加到组合中
sb.append(str.charAt(i));
// 递归生成下一个数字的组合
backTracking(digits, index + 1);
// 回溯，删除最后一个字符，以便尝试下一个字母
sb.deleteCharAt(sb.length() - 1);
}
}
}
此题还有一个基础需要注意：
// 获取digits中的当前数字
int digit = digits.charAt(index) - '0';
这段代码是将字符串 digits 中指定位置 index 的字符转换为数字。它使用了一个常见的技巧，通过将字符 '0' 的 ASCII 值（48）从目标字符的 ASCII 值中减去来实现。
在ASCII编码中，数字字符 '0' 到 '9' 的连续值为 48 到 57。通过将目标字符的 ASCII 值减去字符 '0' 的 ASCII 值，可以得到对应的数字值。
因此，digits.charAt(index) - '0' 的结果将是一个整数，表示 digits 字符串中指定位置的数字字符所对应的数字值。
评论区