跳至主要內容

17. 电话号码的字母组合


17. 电话号码的字母组合open in new window

🟠   🔖  哈希表 字符串 回溯  🔗 力扣open in new window LeetCodeopen in new window

题目

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括号生成open in new window[✓]字符串 动态规划 回溯
39组合总和open in new window[✓]数组 回溯
401二进制手表open in new window位运算 回溯
2266统计打字方案数open in new window哈希表 数学 字符串 1+
3014输入单词需要的最少按键次数 Iopen in new window贪心 数学 字符串
3016输入单词需要的最少按键次数 IIopen in new window贪心 哈希表 字符串 2+