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.
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
|
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
|
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;
};
|