Voyz's Studio.

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

字数统计: 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.

Snip20200728_2.png

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 加入到结果中。

Snip20200728_3.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
* @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;
};

Snip20200728_4.png

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