Phone letter combinations (backtracking)

Medium TimeO(4ⁿ) letters SpaceO(n) stack

On an old phone keypad 2 spells abc, 3 spells def, and so on up to 9, so a string of digits could stand for many different words. Given digits, a string of digits from 2 to 9, return every letter combination the number could spell. One letter is taken from each digit, keeping the digits' order; 0 and 1 carry no letters, and an empty input spells nothing at all.

Examples

Example 1

Input
digits = '23'
Output
["ad","ae","af","bd","be","bf","cd","ce","cf"]
abc against def: 3 × 3 = 9 combinations, the first digit's letter always first.

Example 2

Input
digits = ''
Output
[]
No digits, so nothing is spelled — not even the empty string.

The Code

function backtrack(index, digits, current, mapping, result) {
  if (index === digits.length) {
    result.push(current);
    return;
  }
  const letters = mapping[digits[index]];
  for (let i = 0; i < letters.length; i++) {
    backtrack(index + 1, digits, current + letters[i], mapping, result);
  }
}
function letterCombinations(digits) {
  if (digits.length === 0) return [];
  const mapping = {
    '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
    '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
  };
  const result = [];
  backtrack(0, digits, '', mapping, result);
  return result;
}
letterCombinations('23');
Done

The first 8 calls, of 30. This one does not fit on a page.

Step through letterCombinations('23') call by call

More like this

All backtracking examples (10) →