题目描述

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

我的解法

思路比较简单，构造一个子函数getLettersList，传入前置字母letter和数字串strDigits。 取出数字串的第一个数字firstNum，然后判断剩余数字子串subDigits的长度。 如果剩余数字子串长度等于0，那么遍历firstNum对应的字母数组，用letter加上每个元素，放入到answerList里并返回； 如果剩余数字子串长度大于0，那么遍历firstNum对应的字母数组，用letter加上每个元素与subDigits当做新的参数，调用getLettersList，将结果拼接到answerList里并返回。 这样子函数就完成了。 父函数则还需要对空输入做特殊处理，判断输入为空时返回空数组。 代码如下：

var letterCombinations = function(digits) {
    if (digits.length === 0) {
        return [];
    }

    const numToLetters = {
        '2': ['a', 'b', 'c'],
        '3': ['d', 'e', 'f'],
        '4': ['g', 'h', 'i'],
        '5': ['j', 'k', 'l'],
        '6': ['m', 'n', 'o'],
        '7': ['p', 'q', 'r', 's'],
        '8': ['t', 'u', 'v'],
        '9': ['w', 'x', 'y', 'z'],
    }
    return getLettersList('', digits);

    function getLettersList(letter, strDigits) {
        const firstNum = strDigits.slice(0, 1);
        const subDigits = strDigits.slice(1);
        let answerList = [];
        if (subDigits.length === 0) {
            for (let i = 0; i < numToLetters[firstNum].length; i++) {
                answerList.push(letter + numToLetters[firstNum][i]);
            }
            return answerList;
        } else {
            for (let i = 0; i < numToLetters[firstNum].length; i++) {
                const ans = getLettersList(letter + numToLetters[firstNum][i], subDigits);
                answerList = answerList.concat(ans);
            }
            return answerList;
        }
    }
};

// Runtime: 88 ms, faster than 47.66% of JavaScript online submissions for Letter Combinations of a Phone Number.
// Memory Usage: 42.3 MB, less than 20.42% of JavaScript online submissions for Letter Combinations of a Phone Number.

优秀解法

直接贴上按优秀解法修改后的代码：

var letterCombinations = function(digits) {
    if (digits.length === 0) {
        return [];
    }

    const numToLetters = {
        '2': 'abc',
        '3': 'def',
        '4': 'ghi',
        '5': 'jkl',
        '6': 'mno',
        '7': 'pqrs',
        '8': 'tuv',
        '9': 'wxyz',
    }
    const result = [];
    getLettersList('', 0)
    return result;

    function getLettersList(letter, digitsIndex) {
        if (digitsIndex === digits.length - 1) {
            for (const numLetter of numToLetters[digits[digitsIndex]]) {
                result.push(letter + numLetter);
            }
            return;
        }
        for (const numLetter of numToLetters[digits[digitsIndex]]) {
            getLettersList(letter + numLetter, digitsIndex + 1);
        }
    }
};
// Runtime: 61 ms, faster than 94.02% of JavaScript online submissions for Letter Combinations of a Phone Number.
// Memory Usage: 42.1 MB, less than 56.40% of JavaScript online submissions for Letter Combinations of a Phone Number.

优秀解比原做法有两处优化：将numToLetters的value从数组改成了字符串；优化子函数，避免使用中间变量strDigits和answerList。 在尝试优化的过程中也发现了我的解法中的优秀的地方：对于尾迭代进行了优化，避免了多调用一次函数。

本题中子函数用到的算法是深度优先遍历。由于本题答案需要全解，所以中间可优化的点比较少。