Skip to content

017. Letter Combinations of a Phone Number

难度: Medium

刷题内容

原题连接

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

内容描述

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

img

Example:

 Input: "23"
 Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:

Although the above answer is in lexicographical order, your answer could be in any order you want.

解题方案

递归版本 **- 时间复杂度: O(N²)*- 空间复杂度: O(N)***

代码:

/**
 * 递归函数
 * @param digits 传入的数字
 * @param index 当前是第几个数字
 * @param str 当前已拼装的字符串
 * @param list 结果集
 */
let helper = function (digits, index, str, list) {
    let map = {
        2: 'abc',
        3: 'def',
        4: 'ghi',
        5: 'jkl',
        6: 'mno',
        7: 'pqrs',
        8: 'tuv',
        9: 'wxyz'
    };
    if (str.length === digits.length) {
        list.push(str);
        return false;
    }
    let strs = map[digits[index]];
    for (let i = 0; i < strs.length; i++) {
        helper(digits, index + 1, str + strs.charAt(i), list)
    }
};
let letterCombinations = function (digits) {
    let list = [];
    if (digits) {
        helper(digits, 0, '', list);
    }
    return list;
};

非递归版本 **- 时间复杂度: O(N²)*- 空间复杂度: O(N)***

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


回到顶部