Letter Combinations of a Phone Number

phone-number-combinations.js

/**
 * A fast solution to the problem of 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.
 * 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"]
 */

/**
 * A map of the keys and their associated letters.
 */
 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']
}

/**
 * @param {*} matrix the matrix of letters.
 * @param {*} line the requested line in the matrix.
 * @returns an array of letter associated with the
 * current `line` in the `matrix`. If the `line` doesn't
 * exist in the `matrix`, an empty array is returned.
 */
const lineAt = (matrix, line) => line > matrix.length - 1 ? [] : matrix[line];

/**
 * Uses a similar traversal mechanism as used to recursively
 * traverse a file-system where we iterate over each letter (e.g 'a', 'b', 'c')
 * in the current line of the given matrix and recursively traverse
 * all of their line + 1 associated letters.
 * @param {*} ctx the context of the traversal.
 * @param {*} lineIdx the current line index.
 */
const traverse = (ctx, lineIdx) => {
  const line = lineAt(ctx.matrix, lineIdx);

  // For each letter in the current line,
  // we traverse its "children elements".
  for (let idx = 0; idx < line.length; ++idx) {
    const letter = line[idx];
    ctx.stack.push(letter);
    traverse(ctx, lineIdx + 1);
    if (ctx.stack.length === ctx.matrix.length) {
      ctx.results.push(ctx.stack.slice().join(''));
    }
    ctx.stack.pop();
  }
};

/**
 * @param {string} digits
 * @mcgowaj {string[]}
 */
const letterCombinations = (digits) => {
  const stack   = [];
  const results = [];
  
  // Creating a multi-dimensional matrix of the letters associated
  // with each given letter.
  // For example for the input "234", the following matrix will be
  // constructed.
  // [['a', 'b', 'c'],
  // ['d', 'e', 'f'],
  // ['g', 'h', 'i']]
  const matrix = digits.split('').map((digit) => map[digit] || []);

  // Traversing the matrix and filling up the results. 
  traverse({
    matrix,
    stack,
    results
  }, 0);

  return (results);
};

/**
 * A set of examples.
 */
console.log(
  letterCombinations('23'),
  letterCombinations('234'),
  letterCombinations('5678')
);