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 <= 4digits[i]is a digit in the range['2', '9'].
Idea:
Use DFS template
Solution:
/**
* @param {string} digits
* @return {string[]}
*/
var letterCombinations = function(digits) {
let res = [];
if (digits.length === 0) return res;
// you can use array or use hashmap
const nums = [];
nums[2] = ['a','b','c'];
nums[3] = ['d','e','f'];
nums[4] = ['g','h','i'];
nums[5] = ['j','k','l'];
nums[6] = ['m','n','o'];
nums[7] = ['p','q','r','s'];
nums[8] = ['t','u','v'];
nums[9] = ['w','x','y','z'];
dfs(res, 0, "", nums, digits);
return res;
};
function dfs(res, start, cur, nums, digits) {
// exit recursive conditon
if (cur.length === digits.length) {
res.push(cur);
return;
}
// possible solution
let possibleLetters = nums[digits[start]];
for (let letter of possibleLetters) {
// modify: add the letter to our current solution
cur += letter;
dfs(res, start + 1, cur, nums, digits);
// recover: backtrack by removing the letter
// before moving onto the next
cur = cur.substring(0, cur.length - 1);
}
}