문제 설명
Given a string containing digits from 2-9
inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.
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 1:
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Example 2:
Input: digits = ""
Output: []
Example 3:
Input: digits = "2"
Output: ["a","b","c"]
Constraints:
0 <= digits.length <= 4
digits[i]
is a digit in the range['2', '9']
.
나의 풀이
소스
/**
* @param {string} digits
* @return {string[]}
*/
var letterCombinations = function(digits) {
const charMap = {
2: ['a', 'b', 'c'],
3: ['d', 'e', 'f'],
4: ['g', 'h', 'i'],
5: ['j', 'k', 'l'],
6: ['m', 'n', 'o'],
7: ['p', 'q', 'r', 's'],
8: ['t', 'u', 'v'],
9: ['w', 'x', 'y', 'z'],
}
let result = [];
for (const digit of digits) {
const charCases = charMap[digit];
if (result.length === 0) {
result = result.concat(charCases);
continue;
}
const newResult = [];
for (const resultString of result) {
for (const charCase of charCases) {
newResult.push(resultString + charCase);
}
}
result = newResult;
}
return result;
};
설명
BFS / DFS 문제인데, 나는 BFS / DFS가 아니라 다른방식으로 풀었다.
문제를 읽고 굳이 BFS / DFS를 써야되는 문제인가 싶었는데,
그 이유는 그냥 나올 수 있는 경우의 수를 모두 구하면 되기 때문이다. (순열)
result 배열에 다음 숫자에 매핑되는 문자들을 더해가면서 나올 수 있는 경우의 수를 계속 축적해나가면 끝.
다른사람의 풀이
재귀를 사용한 순열 풀이
var letterCombinations = function(digits) {
if(!digits.length) return [];
const map = {
2: ['a', 'b', 'c'],
3: ['d', 'e', 'f'],
4: ['g', 'h', 'i'],
5: ['j', 'k', 'l'],
6: ['m', 'n', 'o'],
7: ['p', 'q', 'r', 's'],
8: ['t', 'u', 'v'],
9: ['w', 'x', 'y', 'z'],
}
const result = [];
function permute(str, idx) {
if(idx === digits.length) {
result.push(str);
return;
}
for(let alpha of map[digits[idx]]) {
permute(str+alpha, idx+1);
}
}
permute('', 0);
return result;
};
BFS를 사용한 풀이 (별로인 것 같다)
var letterCombinations = function (digits) {
if (digits.length === 0) return [];
let table = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];
let stack = [];
let res = [""];
digits = digits.split("");
for (i = 0; i < digits.length; i++) digits[i] = parseInt(digits[i], 10);
for (num of digits) stack.push(table[num].split(""));
while (stack.length > 0) {
let len = res.length;
for (i = 0; i < len; i++) {
for (ltr of stack[0]) {
res.push(res[i] + ltr);
}
}
stack.shift();
}
res = res.filter((el) => {
return el.length === digits.length
})
return res;
};