0017._Letter_Combinations_Of_A_Phone_Number

017. Letter Combinations of a Phone Number

难度: Medium

刷题内容

原题连接

内容描述

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)**

代码:

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
32
33
34
/**
* 递归函数
* @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)**

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
32
33
34
/**
* @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;
};