17. 电话号码的字母组合

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

方法一：dfs+回溯

时间复杂度：O(3^m+4^n)，m和n分别是3个字母和4个字母对应的数字个数

空间复杂度：O(m+n)

 1 /**
 2  * @param {string} digits
 3  * @return {string[]}
 4  */
 5 var letterCombinations = function(digits) {
 6     if (digits.length === 0) {
 7         return [];
 8     }
 9     const res = [];
10     const map = { //建立电话号码和字母的映射关系
11         '2': 'abc',
12         '3': 'def',
13         '4': 'ghi',
14         '5': 'jkl',
15         '6': 'mno',
16         '7': 'pqrs',
17         '8': 'tuv',
18         '9': 'wxyz'
19     }
20     const dfs = (curStr, i) => { //curStr是递归每一层的字符串，i是扫描的指针
21         if (i > digits.length - 1) { //边界条件，递归的出口
22             res.push(curStr); //其中一个分支的解推入res
23             return; //结束递归分支，进入另一个分支
24         }
25         const letters = map[digits[i]]; //取出数字对应的字母
26         for (const letter of letters) {
27             //进入不同字母的分支
28             dfs(curStr + letter, i + 1) //参数传入新的字符串，i右移，继续递归
29         }
30     }
31     dfs('', 0); //递归入口，传入空字符串，i初始为0的位置
32     return res;
33 }