LeetCode算法笔记--电话号码的字母组合

算法题热题HOT100 回溯算法

字数统计: 251阅读时长: 1 min

 2020/11/28   Share

LeetCode算法笔记–Day32

17. 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.

example
input: “23”
output: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].

My Answer：

定义函数 backtrack(combination, nextdigit)，当nextdigit 非空时，对于 nextdigit[0] 中的每一个字母 letter，执行回溯 backtrack(combination + letter,nextdigit[1:]，直至 nextdigit 为空。最后将 combination 加入到结果中。

/**
 * @param {string} digits
 * @return {string[]}
 */
let _mapping = new Map();
_mapping.set('2','abc')
_mapping.set('3','def')
_mapping.set('4','ghi')
_mapping.set('5','jkl')
_mapping.set('6','mno')
_mapping.set('7','pqrs')
_mapping.set('8','tuv')
_mapping.set('9','wxyz')

var letterCombinations = function(digits) {
    if(digits.length == 0) return[];
    let _output = [];

    let backtrace = function(combine,_nextDigits){
        if(_nextDigits.length == 0){
            _output.push(combine)
        }else{
            for(let _letter of _mapping.get(_nextDigits[0])){
                backtrace(combine+_letter,_nextDigits.substring(1))
            }
        }
    }

    backtrace('',digits)
    return _output;
};

Next Post

LeetCode算法笔记--删除链表的倒数第N个节点
Previous Post

LeetCode算法笔记-滑动窗口——最长不重复子字符串长度

CATALOG

1. LeetCode算法笔记–Day32
2. 17. Letter Combinations of a Phone Number
1. 2.0.0.0.1. 题目：
2. 2.0.0.0.2. My Answer：

