Letter Combinations of a Phone Number

The problem

A phone keypad puts letters on the digits 2 to 9: 2 has abc, 3 has def, 4 has ghi, 5 has jkl, 6 has mno, 7 has pqrs, 8 has tuv and 9 has wxyz. You are given digits, a string of such digits. Return every string you can make by choosing one letter for each digit, with the letters in the same order as their digits. The strings may come in any order. If digits is empty, return an empty list.

What to write

function solve(digits: string): string[]

Input
digits = "23"

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

Input
digits = ""

Output
[]

Constraints

0 ≤ digits.length ≤ 4.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   There are at most 4 digits and a key carries at most 4 letters, so the answer never has more than 4 × 4 × 4 × 4 = 256 strings. Listing every one of them is cheap. Watch the empty input: it must give an empty list.

2. Hint 2: Ask a smaller question

   Write out the answer for the single digit 2. Then write it out for 23. Put the two lists side by side: how can you get the second list from the first one and the letters d, e and f?

3. Hint 3: Name the pattern

   Each string is a row of choices, one letter per digit, and you must return every such row. That is the signal for backtracking, which tries the choices in turn. Here no choice limits another, so one loop can make each choice for all strings at once: extend every string so far with each letter of the next digit. Read the lesson on backtracking.

4. Hint 4: State the invariant

   After you have handled the first k digits, the list holds every string of k letters that takes its first letter from the first digit, its second from the second digit, and so on, each exactly once. Before any digit, that is the one empty string.

5. Hint 5: Sketch the pseudocode

   If digits is empty, return an empty list. Let strings be a list holding one empty string. For each digit of digits, from left to right: make a new empty list; for each string and each letter of that digit, add string plus letter to the new list; then let strings be the new list. Return strings.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Extend every current prefix with every letter assigned to the next digit.

The slow way

Write one loop per digit: for two digits, a loop over the first digit's letters with a loop over the second digit's letters inside it. That gives the right strings for two digits. But the number of loops is fixed in the code, while digits can hold anything from zero to four digits, so each length would need its own version.

The insight

You do not need to know the number of digits in advance. Handle one digit at a time. If you hold every string for the digits so far, then the strings for one more digit are each of those strings with each letter of the new digit added at the end.

Step by step

1. No digits: return an empty list. With no digits there is no letter to choose, and the expected answer is an empty list. Without this test the steps below would return their starting list, which holds one empty string.
2. Write down the letters that each digit's key carries. A digit does not tell you its letters, and the keys are not regular: 7 and 9 carry four letters, the others three. A table states them plainly.
3. Start with one string: the empty one. The empty string is the one way to choose letters for no digits, and it gives the first digit something to extend. Starting with an empty list would leave nothing to extend, and the answer would stay empty.
4. Take the digits one at a time, from left to right. The letters of a string must follow the order of the digits. Going from left to right and always adding at the end keeps that order.
5. Extend every string so far with every letter of this digit. Any choice made so far can be followed by any letter of this digit, because no letter rules out another. So each string so far gives one longer string per letter, collected in a new list.
6. Replace the old strings with the longer ones. The old strings are one letter short and are not answers. Only their longer versions go on to the next digit, so the new list takes the place of the old one.
7. After the last digit, the list holds every combination. Each round added one letter for one digit to every string. So now every string has exactly one letter per digit, in order, and every way of choosing the letters is in the list.

The same numbered steps are the comments in each solution.

function solve(digits) {
  // 1. No digits: return an empty list
  if (!digits) return [];
  // 2. Write down the letters that each digit's key carries
  const keys = {
    "2": "abc",
    "3": "def",
    "4": "ghi",
    "5": "jkl",
    "6": "mno",
    "7": "pqrs",
    "8": "tuv",
    "9": "wxyz",
  };
  // 3. Start with one string: the empty one
  let out = [""];
  // 4. Take the digits one at a time, from left to right
  for (const d of digits) {
    // 5. Extend every string so far with every letter of this digit
    const longer = [];
    for (const prefix of out) {
      for (const ch of keys[d]) longer.push(prefix + ch);
    }
    // 6. Replace the old strings with the longer ones
    out = longer;
  }
  // 7. After the last digit, the list holds every combination
  return out;
}

function solve(digits: string): string[] {
  // 1. No digits: return an empty list
  if (!digits) return [];
  // 2. Write down the letters that each digit's key carries
  const keys: Record<string, string> = {
    "2": "abc",
    "3": "def",
    "4": "ghi",
    "5": "jkl",
    "6": "mno",
    "7": "pqrs",
    "8": "tuv",
    "9": "wxyz",
  };
  // 3. Start with one string: the empty one
  let out = [""];
  // 4. Take the digits one at a time, from left to right
  for (const d of digits) {
    // 5. Extend every string so far with every letter of this digit
    const longer: string[] = [];
    for (const prefix of out) {
      for (const ch of keys[d]) longer.push(prefix + ch);
    }
    // 6. Replace the old strings with the longer ones
    out = longer;
  }
  // 7. After the last digit, the list holds every combination
  return out;
}

def solve(digits):
    # 1. No digits: return an empty list
    if not digits:
        return []
    # 2. Write down the letters that each digit's key carries
    keys = {
        "2": "abc",
        "3": "def",
        "4": "ghi",
        "5": "jkl",
        "6": "mno",
        "7": "pqrs",
        "8": "tuv",
        "9": "wxyz",
    }
    # 3. Start with one string: the empty one
    result = [""]
    # 4. Take the digits one at a time, from left to right
    for digit in digits:
        # 5. Extend every string so far with every letter of this digit
        longer = []
        for prefix in result:
            for letter in keys[digit]:
                longer.append(prefix + letter)
        # 6. Replace the old strings with the longer ones
        result = longer
    # 7. After the last digit, the list holds every combination
    return result

Example 1, traced

Input
digits = "23"

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

Why it works

Before the first digit the list holds the one string of no letters. Each round replaces every string by its extensions with each letter of the next digit. So after k digits the list holds every way to choose one letter for each of the first k digits, each exactly once. After the last digit, that is the whole answer.

Time and space

Time O(n · 4^n), extra space O(n · 4^n). A key has at most 4 letters, so n digits give at most 4^n strings, each n letters long. Writing them takes O(n · 4^n) time and storing them takes O(n · 4^n) space. The shorter lists built on the way add up to less than the final list.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Handle the empty input before the loop. The method starts from a list holding one empty string, so with no digits it would return that list, and the expected answer is a list with nothing in it.
• Replace the list after each digit, do not add to it. If the old strings stay, example 1 returns 16 strings instead of 9, among them the empty string and single letters such as a and d.
• Do not compute the letters from the digit by arithmetic. Keys 7 and 9 carry four letters. A formula that gives every key three letters returns p, q, r for the digit 7 and loses s.

Pattern

Backtracking. Builds on Subsets.

Keep going