一：题目描述：

给定一个仅包含数字 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'] 的一个数字。

---

三：思路

回溯

对于这种不同集合之间的组合，一开始会去想着，两个集合用两个for循环，三个集合三个for循环，但是我们无法去控制几个for循环，所以就想到用递归来控制for循环，再想到组合问题也需要用到回溯

• 利用一个数组存储对应的下标的字符
• 可以模拟构建一个树形结构
• 横向拓展由for循环控制对digit的遍历
• 纵向拓展由递归函数进行回溯
• 需要注意该题是两个集合的组合，不是一个集合的组合，考虑用index变量控制

四：代码 + 复杂度分析

回溯+剪枝

/*** @param {string} digits* @return {string[]}*/
var letterCombinations = function(digits) {//回溯//用数组下标对应字符const map = ["", "", "abc", "def", "ghi","jkl", "mno", "pqrs", "tuv", "wxyz"]if(digits.length === 0) return []if(digits.length === 1) return map[digits].split("")//存储结果const res = []//单个结果const path = []const backtracking = (digits, index) => {if(digits.length === path.length) {//拼接起来//adconsole.log(path)res.push(path.join(''))return }for(let i of map[digits[index]]) {//['a', 'd']path.push(i)backtracking(digits, index + 1)path.pop()}}backtracking(digits, 0)return res
};

• 时间复杂度：O(3 ^ m * 4 ^ m)

  • 在最坏情况下，每个数字都映射到一个包含 3 或 4 个字符的集合（例如，数字 ‘2’ 对应 “abc”，数字 ‘7’ 对应 “pqrs”）。

• 空间复杂度: O(n + k)

  • res 数组用于存储最终的字母组合，因此其空间复杂度是 O(k)，其中 k 表示可能的字母组合数量。
  • path 数组用于存储当前的组合路径，它的最大长度等于输入数字字符串的长度，因此其空间复杂度为 O(n)，其中 n 表示输入数字字符串的长度。