17. [✔][M]电话号码的字母组合

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

---

题解：

回溯算法套路

/*
 * @lc app=leetcode.cn id=17 lang=typescript
 *
 * [17] 电话号码的字母组合
 */

// @lc code=start
function letterCombinations(digits: string): string[] {
    if (!digits) {
        return []
    }

    const map = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];
    let res: string[] = [];

    const backtrack = (digits: string, start: number, track: string[]) => {
        if (track.length === digits.length) {
            res.push(Array.from(track).join(""));
            return;
        }

        for (let i = start; i < digits.length; i++) {
            const digit = digits[i];
            for (const ch of map[parseInt(digit)]) {
                track.push(ch);
                backtrack(digits, i + 1, track);
                track.pop();
            }
        }
    }

    backtrack(digits, 0, []);

    return res;
};
// @lc code=end