17. 电话号码的字母组合

🟠   🔖  哈希表 字符串 回溯  🔗 力扣 LeetCode

题目

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 不对应任何字母。

解题思路

1. 数字与字母的映射关系： 首先，需要建立数字与字母的映射关系，即 2 对应 "abc"，3 对应 "def"，以此类推。可以使用一个数组或对象来存储这种映射关系。

2. 回溯过程： 定义一个回溯函数 backtrack，接收当前需要处理的数字索引 index 和当前已生成的字符串 current 作为参数。

3. 终止条件： 在回溯的过程中，需要判断当前字符串的长度是否等于输入数字字符串的长度。如果相等，则将当前字符串加入结果集。

4. 递归调用： 在回溯过程中，根据当前数字的映射关系，逐个尝试每个对应的字母。对于当前数字的每个映射字母，都可以选择加入当前字符串，然后递归调用下一层，之后需要撤销当前选择，继续尝试下一个映射字母。

5. 循环遍历： 对于当前数字的每个映射字母，通过循环遍历的方式实现，确保每个字母都被考虑到。

6. 返回结果： 最终通过调用 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+	🟠	🀄️ 🔗