Letter Combinations of a Phone Number

1. Define the problem

Letter Combinations of a Phone Number

Given a string of digits from 2-9, return all possible letter combinations that the number could represent, using the classic telephone keypad mapping (2 maps to "abc", 3 maps to "def", and so on). Return the answer in any order. Use backtracking that fills one digit position at a time: try each letter the current digit maps to, recurse into the next digit, then undo the letter so the next one at this position can be tried.

Constraints

0 ≤ digits.length ≤ 4
digits_i is a digit in the range ["2", "9"]

Example

Inputdigits = "23"

Output["ad","ae","af","bd","be","bf","cd","ce","cf"]

Explanation 2 maps to "abc" and 3 maps to "def", giving 3 × 3 = 9 combinations.

2. Visualize the solution

Try each letter for the current digit, undo to try the next one

Statustry

Digit 0 ("2") tries letter a: path="a".

What happens in this step

path = "a"
choice: digit 0 letter 'a', try continuing

backtrack(0) looks up map["2"]="abc" and tries the first letter, 'a'. It's pushed onto path, and backtrack(1) is called for the next digit.

Step 1 of 5

Steps to visualize

Look up the letters the current digit maps to.
Try one letter, add it to the path, and recurse into the next digit.
Once every digit position has a letter, record the path as one combination.
Undo the last letter so the current digit position can try its next letter.

3. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Try each letter for the current digit, undo to try the next one

Statustry

Digit 0 ("2") tries letter a: path="a".

What happens in this step

path = "a"
choice: digit 0 letter 'a', try continuing

backtrack(0) looks up map["2"]="abc" and tries the first letter, 'a'. It's pushed onto path, and backtrack(1) is called for the next digit.

Step 1 of 5

4. Solution

Solution

solution.tsTypeScript

function letterCombinations(digits) {
  if (digits.length === 0) {
    return [];
  }

  const map = {
    2: 'abc',
    3: 'def',
    4: 'ghi',
    5: 'jkl',
    6: 'mno',
    7: 'pqrs',
    8: 'tuv',
    9: 'wxyz',
  };

  const result = [];
  const path = [];

  function backtrack(index) {
    if (index === digits.length) {
      result.push(path.join(''));
      return;
    }

    const letters = map[digits[index]];
    for (const letter of letters) {
      path.push(letter);
      backtrack(index + 1);
      path.pop();
    }
  }

  backtrack(0);
  return result;
}

Time: O(4^n · n)
Space: O(n)

5. Test cases

Test cases

Input	Expected	Covers
`digits = "23"`	`["ad","ae","af","bd","be","bf","cd","ce","cf"]`	example from the docstring
`digits = ""`	`[]`	empty input returns no combinations
`digits = "2"`	`["a","b","c"]`	single digit, three letters
`digits = "9"`	`["w","x","y","z"]`	single digit with four letters
`digits = "79"`	`16 combinations of pqrs and wxyz`	both digits map to four letters, 16 combinations
`digits = "5"`	`["j","k","l"]`	single digit, three letters, different mapping
`digits = "45"`	`["gj","gk","gl","hj","hk","hl","ij","ik","il"]`	two digits that both map to three letters

Letter Combinations of a Phone Number