LeetCode-17-电话号码的字母组合

一：题目描述：

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

二：示例与提示

示例 1:

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
1
2

示例 2:

输入：digits = ""
输出：[]
1
2

示例 3:

输入：digits = "2"
输出：["a","b","c"]
1
2

提示：

• 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) {
            //拼接起来
            //ad
            console.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
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

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

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

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

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