17.电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入： digits = “23”
输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]
示例 2：
输入： digits = “”
输出：[]
示例 3：
输入： digits = “2”
输出：[“a”,“b”,“c”]
提示：
- 0 ≤ d i g i t s . l e n g t h ≤ 4 0 \leq digits.length \leq 4 0≤digits.length≤4
digits[i]是范围['2', '9']的一个数字。
解法一(回溯)
思路分析：
- 根据题意，该题为字母组合问题，使用回溯算法来解决
- 首先是回溯三要素
- 思考返回值和参数，因为题目要求获得字符组合，并不需要返回值，即返回类型为
void，然后需要一个参数来表示当前递归的高度，其余参数需要时再添加 - 思考递归结束条件，即当递归高度与字符串
digits长度一致时，保存记录的字符组合，并结束该层递归 - 思考回溯的一般过程，即根据递归高度确定所需遍历的字符串，然后进行组合，并继续选择字符，然后执行回溯操作
- 思考返回值和参数，因为题目要求获得字符组合，并不需要返回值，即返回类型为
实现代码如下：
class Solution {
char[][] charArr = new char[][]{
{' '},
{' '},
{'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'}
};
List<String> ans = new ArrayList<>();
StringBuffer path = new StringBuffer();
public List<String> letterCombinations(String digits) {
if (digits.isEmpty())
return ans; // 特殊情况
backtracking(digits.length(), 0, digits);
return ans;
}
private void backtracking(int high, int currentHigh, String digits) {
if (currentHigh == high) {
// 获得一个字符组合
ans.add(path.toString());
return ;
}
// 根据当前递归高度 获取待选取的字符数组
int index = digits.charAt(currentHigh) - '0';
for (char ch : charArr[index]) {
path.append(ch);
backtracking(high, currentHigh+1, digits);
path.deleteCharAt(path.length()-1);
}
}
}
提交结果如下：
解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:41.2 MB,击败了14.59% 的Java用户
复杂度分析：
- 时间复杂度：
O
(
n
×
m
)
O(n \times m)
O(n×m)，
n是字符串digits的长度，m是数字所代表的字母数目 - 空间复杂度：
O
(
n
)
O(n)
O(n)，即
digits的长度