LeetCode-17-电话号码的字母组合

字符串 回溯算法

原题地址：电话号码的字母组合

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

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

示例:

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

说明:

尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

解答

只需要遍历输入的数字，将每个数字对应的字母与前面的字母组合即可：

/**
 * @param {string} digits
 * @return {string[]}
 */
const letterCombinations1 = function(digits) {
    const letters = ['abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz'];
    let result = [];
    for (let i = 0; i < digits.length; i ++) {
        // 得到当前数字所对应的字母数组
        let subArray = letters[digits[i] - 2].split('');
        if (result.length === 0) {
            // 如果是第一个数字，直接得到字母数组
            result = subArray;
        } else {
            // 拆开组合
            result = result.map(item => subArray.map(item2 => `${item}${item2}`)).join().split(',')
        }
    }
    return result;
};

测试：

let start = new Date();
const test = letterCombinations1;
console.log(test('23')); // [ 'ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf' ]
console.log(new Date().getTime() - start.getTime()); // 5

时间复杂度： 时间复杂度为O($3^n$ x $4^m$)，其中n是输入数字中对应字母为3的数量，m是对应字母为4的数量
空间复杂度： 与时间复杂度相同，为O($3^n$ x $4^m$)

本文由 李海平 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Jul 28,2019