电话号码的字母组合

[Cosen95]

leetcode: https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/

[Cosen95]

题目难度medium，涉及到的算法知识有递归、回溯。

题目描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。 示例:

输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

思路分析

首先用一个对象map存储数字与字母的映射关系，接下来遍历对应的字符串，第一次将字符串存在结果数组result中，第二次及以后的就双层遍历生成新的字符串数组。

代码实现

哈希映射 逐层遍历

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {
    let res = [];
    if (digits.length === 0) return []
    let map = {
        2: 'abc',
        3: 'def',
        4: 'ghi',
        5: 'jkl',
        6: 'mno',
        7: 'pqrs',
        8: 'tuv',
        9: 'wxyz'
    }
    for (let num of digits) {
        let chars = map[num]
        if (res.length > 0) {
            let temp = []
            for (let char of chars) {
                for (let oldStr of res) {
                    temp.push(oldStr + char)
                }
            }
            res = temp
        } else {
            res.push(...chars)
        }

    }
    return res
};

递归

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {
    let res = [];
    if (!digits) return []
    let map = {
        2: 'abc',
        3: 'def',
        4: 'ghi',
        5: 'jkl',
        6: 'mno',
        7: 'pqrs',
        8: 'tuv',
        9: 'wxyz'
    }
    function generate(i, str) {
        let len = digits.length;
        if (i === len) {
            res.push(str)
            return
        }
        let chars = map[digits[i]]
        for (let j = 0; j < chars.length; j++) {
            generate(i+1, str + chars[j])
        }
    }
    generate(0, '')
    return res
};