电话号码的字母组合

[Bulandent]

难度：中等
来源：17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

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

示例:

输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

思路：

• 一看到题目里提到的任意组合就应该立刻想到使用回溯算法；
• 回溯算法的核心就是第一要找到路径，第二要选择列表，第三要知道结束条件是什么。
• 理解了以上这3点，然后就很好的应用到实际例子里了。

题解：

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {
    if (digits.length === 0) return []
    const map = {
        2: 'abc',
        3: 'def',
        4: 'ghi',
        5: 'jkl',
        6: 'mno',
        7: 'pqrs',
        8: 'tuv',
        9: 'wxyz'
    }
    let res = []
    const dfs = (curStr, index) => {
        if (index > digits.length - 1) {
            res.push(curStr)
            return
        }
        let letters = map[digits[index]]
        for (let l of letters) {
            dfs( curStr + l, index + 1)
        }
    }
    dfs('', 0)
    return res
};