Site icon JS Tech Road

LeetCode 17. Letter Combinations of a Phone Number (javascript)

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:

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);
    }
}
Exit mobile version