学习记录：js算法（八十九）：电话号码的字母组合

电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
如图

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

示例 2：
输入：digits = ""
输出：[]

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

思路一

function letterCombinations(digits) {
    if (digits.length === 0) return [];
    const res = [];
    const phoneMap = {
        '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
        '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
    };
    const path = [];

    const backtrack = (index) => {
        if (path.length === digits.length) {
            res.push(path.join(''));
            return;
        }
        const letters = phoneMap[digits[index]];
        for (let i = 0; i < letters.length; i++) {
            path.push(letters[i]);
            backtrack(index + 1);
            path.pop();
        }
    };

    backtrack(0);
    return res;
}

讲解

1. 初始化：创建一个空的结果数组res和一个空的路径数组path。定义一个映射phoneMap，将数字映射到对应的字母。
2. 递归函数：定义一个递归函数backtrack，它接受以下参数：
   ○ 当前路径path，
   ○ 剩余数字的字符串digits，
   ○ 当前处理的数字的索引index。
3. 基本结束条件：如果index等于digits的长度，意味着我们已经生成了一个完整的组合，此时将当前路径path拷贝一份加入结果数组res，然后返回。
4. 回溯过程：对于从index开始的每一个字母，执行以下操作：
   ○ 获取当前数字对应的字母列表。
   ○ 对于列表中的每一个字母，将其添加到路径path中。
   ○ 调用backtrack函数，传递更新后的path和下一个数字的索引。
   ○ 回溯，即将当前字母从路径path中移除。
5. 开始回溯：调用backtrack函数，传入初始的path、digits和开始位置0。
6. 返回结果：最后返回结果数组res。