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