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

17. 电话号码的字母组合

原题

输入：[['a', 'b'], ['n', 'm'], ['0', '1']] 
输出：["an0", "an1", "am0", "am1", "bn0", "bn1", "bm0", "bm1"]

const combine = function (input) {
    let first = input.shift();
    return input.reduce((memo, current) => {
        let res = [];
        current.forEach(v => {
            memo.forEach(item => {
                res.push(`${item}${v}`);
            });
        });
        return res;
    }, first);
}

leetcode 上倒是有一个类似的 https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number 输入：[['a','b', 'c'],['d', 'e', 'f']] 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

解法是一样的

let input = [['a','b', 'c'],['d', 'e', 'f']];
let first = input.shift();
let result = input.reduce((memo, current) => {
    let res = [];
    current.forEach(v => {
        memo.forEach(item => {
            res.push(`${item}${v}`)
        });
    });
    return res;
}, first);

还是需要使用函数来解决

感觉这个写的很牛逼 来源

const letterCombinations = (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 = [];
    queue.push('');
    for (let i = 0; i < digits.length; i++) { // bfs的层数，即digits的长度
        const levelSize = queue.length;         // 当前层的节点个数
        // console.log(levelSize) 在 digits 为 23 的时候，总共执行两次输出，一次是1，一次是3
        for (let j = 0; j < levelSize; j++) {   // 逐个让当前层的节点出列
           
            // 这里在每次更新 queue 的时候，会动态更新 levelSize
            // 然后会进入到这里，然后从 queue 从取出一个值
            // 然后执行 for (const l of letters) 进行拼接
            // 能把这一步想到，作者真是很牛逼（是一个 BFS 的概念）
            
            // 每次更新 queue 的时候，也是一次回溯的概念
            // 在 const levelSize = queue.length; 下面输出，
            // 在 digits 为 23 的时候，会发现总共执行两次输出，一次是1，一次是3
            const curStr = queue.shift();         // 出列

            const letters = map[digits[i]];

            for (const l of letters) {
                queue.push(curStr + l); // 生成新的字母串入列
            }
        }
    }
    return queue; // 队列中全是最后一层生成的字母串
};

作者使用的 DFS 的解法

感觉 DFS 的更好理解啊

const letterCombinations = digits => {
    if (digits.length === 0) {
        return [];
    }
    
    const res = [];
    const map = { '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz' };
    
    const dfs = (curStr, i) => {
        if (i > digits.length - 1) {
            res.push(curStr);
            return;
        }
        
        const letters = map[digits[i]];
        for (const letter of letters) {
            dfs(curStr + letter, i + 1);
        }
    };            
      
    dfs('', 0);
    return res;
}