Letter combinations of a phone number

Home | Coding Interviews | Searching and Sorting | 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. Return the answer in any order.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {
    if (!digits.length) {
        return [];
    }
    
    const digitToLetters = {
        '2': 'abc',
        '3': 'def',
        '4': 'ghi',
        '5': 'jkl',
        '6': 'mno',
        '7': 'pqrs',
        '8': 'tuv',
        '9': 'wxyz'
    };
    
    const res = [];
    
    function backtrack(idx, comb) {
        if (idx === digits.length) {
            res.push(comb);
            return;
        }
        
        for (const letter of digitToLetters[digits[idx]]) {
            backtrack(idx + 1, comb + letter);
        }
    }
    
    backtrack(0, "");
    
    return res;    

    //in video above, BFS is used instead of dfs/backtracking
    const map = digitToLetters;
    cont queue = ['']
    for (const digit of digits) {
      const len = queue.length;
      for (let i = 0; i<len; i++) {
        const current = queue.shift();
        map[digit].split('').forEach(i => queue.push(current+i))
      }
    }
    return queue;
    
};

Posted by Jamie Meyer 21 days ago