求star

题目#

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

题解:key:#

①回溯#

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function (digits) {
    const table = {
        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']
    }
    let res = [],arr = [],len = digits.length
    if(len == 0)  return []
	
    // 生成给定号码的二维数组
    for(let i=0;i<len;i++) {
        arr.push(table[digits[i]])
    }
    let str = ''
	// 回溯函数
    let backTracking = (len,level) => {
        // 终止条件
        if(str.length === len) {
            res.push(str)
            return 
        }
        // 遍历每一层的数组
        for(let i=0;i<arr[level].length;i++){
            str += arr[level][i]
            backTracking(len,level+1) // 遍历下一层
            str = str.slice(0,-1) // 去掉最后一个添加的字符，开始
        }
    }
    backTracking(len,0)
    return res 
};

②BFS#

/**
 * @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' }
    // 维护一个队列 起初让空字符入队
    const queue = ['']
    // 控制层序遍历的深度为`digits.length`
    for(let i=0;i<digits.length;i++){
        const levelSize = queue.length // 当前层的节点个数
        for(let j =0;j<levelSize;j++){ // 当前层节点逐个出列
            const curStr = queue.shift() // 出队
            const letters = map[digits[i]]
            for(const l of letters) {
                queue.push(curStr + l) // 生成新的字母串入列
            }
        }
    }
    return queue // 最终的队列中是 最后一层生成的字符串
};