17. 电话号码的字母组合
17. 电话号码的字母组合
题目
Given a string containing digits from 2-9
inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.
A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Example 1:
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Example 2:
Input: digits = ""
Output: []
Example 3:
Input: digits = "2"
Output: ["a","b","c"]
Constraints:
0 <= digits.length <= 4
digits[i]
is a digit in the range['2', '9']
.
题目大意
给定一个仅包含数字 2-9
的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下(与电话按键相同)。注意 1
不对应任何字母。
解题思路
数字与字母的映射关系: 首先,需要建立数字与字母的映射关系,即
2
对应"abc"
,3
对应"def"
,以此类推。可以使用一个数组或对象来存储这种映射关系。回溯过程: 定义一个回溯函数
backtrack
,接收当前需要处理的数字索引index
和当前已生成的字符串current
作为参数。终止条件: 在回溯的过程中,需要判断当前字符串的长度是否等于输入数字字符串的长度。如果相等,则将当前字符串加入结果集。
递归调用: 在回溯过程中,根据当前数字的映射关系,逐个尝试每个对应的字母。对于当前数字的每个映射字母,都可以选择加入当前字符串,然后递归调用下一层,之后需要撤销当前选择,继续尝试下一个映射字母。
循环遍历: 对于当前数字的每个映射字母,通过循环遍历的方式实现,确保每个字母都被考虑到。
返回结果: 最终通过调用
backtrack
函数得到所有符合条件的字符串组合,返回这些组合的数组作为最终结果。
代码
/**
* @param {string} digits
* @return {string[]}
*/
var letterCombinations = function (digits) {
if (!digits) return [];
const digitToLetters = {
2: 'abc',
3: 'def',
4: 'ghi',
5: 'jkl',
6: 'mno',
7: 'pqrs',
8: 'tuv',
9: 'wxyz'
};
let res = [];
let track = [];
const backtrack = (start) => {
if (track.length == digits.length) {
res.push(track.join(''));
return;
}
for (let i of digitToLetters[digits[start]]) {
track.push(i);
backtrack(start + 1);
track.pop();
}
};
backtrack(0);
return res;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
22 | 括号生成 | [✓] | 字符串 动态规划 回溯 | |
39 | 组合总和 | [✓] | 数组 回溯 | |
401 | 二进制手表 | 位运算 回溯 | ||
2266 | 统计打字方案数 | 哈希表 数学 字符串 1+ | ||
3014 | 输入单词需要的最少按键次数 I | 贪心 数学 字符串 | ||
3016 | 输入单词需要的最少按键次数 II | 贪心 哈希表 字符串 2+ |