LeetCode_回溯算法_简单_17.电话号码的字母组合

1.题目

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1： 输入：digits = “23” 输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]

示例 2： 输入：digits = “” 输出：[]

示例 3： 输入：digits = “2” 输出：[“a”,“b”,“c”]

提示： 0 <= digits.length <= 4 digits[i] 是范围 [‘2’, ‘9’] 的一个数字。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number

2.思路

（1）回溯算法 由题可知，给定的数字字符串的长度不定，如果直接使用循环来在求其对应的字母组合时，循环的层数不能确定，所以此处考虑在循环中使用递归的方法，并且通过分析可知一趟递归结束的条件为遍历完该数字字符串。思路参考回溯算法详解（修订版）。

3.代码实现（Java）

//思路1————回溯算法 class Solution { String[] dic = {"", "*", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; // res 用来保存结果 List<String> res = new LinkedList<>(); // builder 用于保存中间结果 StringBuilder builder = new StringBuilder(); public List<String> letterCombinations(String digits) { int length = digits.length(); //考虑特殊情况 if (length == 0) { return res; } backtrack(digits, 0); return res; } public void backtrack(String digits, int start) { if (builder.length() == digits.length()) { //达到回溯树的叶子节点 res.add(builder.toString()); return; } for (int i = start; i < digits.length(); i++) { int digit = digits.charAt(i) - '0'; for (char c : dic[digit].toCharArray()) { //做选择 builder.append(c); //递归下一层回溯树 backtrack(digits, i + 1); //撤销选择 builder.deleteCharAt(builder.length() - 1); } } } }