17.电话号码的字母组合.md

17. 电话号码的字母组合

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

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

示例 1：

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

示例 2：

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

示例 3：

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

解题思路：

• 数字和字母有映射关系，如2->abc，可以用一个map来存储
• 答案需要得到所有的字母组合，遍历过程可以想象成一个值为空的根节点的树的遍历，比如 “2”，根节点—>a，回溯到根节点，根节点->b，回溯到根节点，根节点->c

回溯/递归需要考虑的问题：

1. 如何判断当前组成的字符串是最后的结果之一

   遍历到digits的最后一个数字，表示已经到叶子节点了，收集该字符串

2. 递归函数return的条件是什么？

   当前的数字不存在，即叶子节点再往下遍历不存在更多的节点

3. 递归函数的参数是什么？

   当前遍历的数字下标；当前已经组成的字符串

const strMap = new Map([
    ['2', 'abc'],
    ['3', 'def'],
    ['4', 'ghi'],
    ['5', 'jkl'],
    ['6', 'mno'],
    ['7', 'pqrs'],
    ['8', 'tuv'],
    ['9', 'wxyz'],
])
/**
 * @param {string} digits
 * @return {string[]}
 */
const letterCombinations = function (digits) {
    const result = [];
    const dfs = (curStr, curDigitIdx) => {
        if (!digits[curDigitIdx]) return;
        const temp = strMap.get(digits[curDigitIdx]);
        for (let str of temp) {
            curStr = curStr + str;
            if (curDigitIdx === digits.length - 1) {
                result.push(curStr);
            }
            dfs(curStr, curDigitIdx + 1);
            curStr = curStr.slice(0, curStr.length - 1);
        }
    }
    dfs('', 0);
    return result;
};