Letter Combinations of a Phone Number

Q: What is the time complexity of Letter Combinations of a Phone Number?

O(4^n · n) for n digits: there can be 4^n strings, when every digit is 7 or 9, and each takes n steps to write. That is the size of the output, so no solution does better. Backtracking needs O(n) extra space besides the output.

MediumBacktracking

+10

On a phone keypad, each digit from 2 to 9 carries a few letters: 2 is abc, 3 is def, 4 is ghi, 5 is jkl, 6 is mno, 7 is pqrs, 8 is tuv and 9 is wxyz.

You get a string digits. Pick one letter for each digit, keeping the digits in their order, and you get one string the keys can type. Return every such string, sorted in lexicographic (dictionary) order.

Function

letterCombinations(digits: string) → string-array

digitsstring: the digits pressed, each from 2 to 9
Returnsstring-array: every string the keys can type, in lexicographic order

Constraints

1 ≤ digits.length ≤ 4
Every character of digits is a digit from 2 to 9.
The answer holds at most 4⁴ = 256 strings.

Examples

Input: digits = "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
Explanation: 2 offers a, b, c and 3 offers d, e, f. Each first letter pairs with each second letter: 3 × 3 = 9 strings, sorted when the first letter changes slowest.

Input: digits = "94"
Output: ["wg", "wh", "wi", "xg", "xh", "xi", "yg", "yh", "yi", "zg", "zh", "zi"]
Explanation: 9 has four letters and 4 has three, so there are 4 × 3 = 12 strings. All three strings that start with w come before the first one that starts with x.

Follow-up

Suppose you only want the combinations that are real words from a dictionary. How would you avoid building all 4^n strings first?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

The answer holds up to 4^n strings, so every solution spends at least that much work writing them. What matters is producing every choice once, with none missed or repeated. That is backtracking over a decision tree with one level per digit, where every leaf is an answer.

Build the strings one digit at a time

Intuition

Start with a list holding one empty string and extend it one digit at a time. For "23", the digit 2 turns it into a, b, c, and 3 grows each of those by d, e and f, giving nine strings.

The order stays sorted. If the list is sorted before a digit, you extend the prefixes in that order, and each prefix by its key's letters from left to right: an earlier prefix still comes first, and equal prefixes are ordered by the new letter.

The work is the size of the answer, but while you build a level, the whole previous level stays in memory too.

Algorithm

Start with combos = [""], one empty prefix.
For each digit, make a new list: for every prefix in combos, and every letter on that digit's key, add prefix + letter.
Replace combos with the new list.
After the last digit, return combos.

KEYPAD = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
          "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}


def letterCombinations(digits):
    combos = [""]  # every prefix built so far; one empty prefix to start
    for digit in digits:
        # Each old prefix grows by each letter of this digit, in order.
        combos = [prefix + letter for prefix in combos for letter in KEYPAD[digit]]
    return combos

Backtracking over the decision tree

Intuition

The answers are the leaves of a decision tree. The root is the empty string, and each level adds one letter of the next digit: for "23" the root has children a, b, c, each with children for d, e, f.

Walk it depth first with one buffer, path. At level i, choose a letter of digits[i] by appending it, explore by recursing on i+1, and undo by removing it. The undo lets one buffer serve the whole tree: after ad, ae and af, popping returns path to a, then to the empty string, ready for b. When i reaches the end of digits, save a copy.

The time is still O(4^n · n), but the extra memory is the buffer and the call stack, O(n).

Algorithm

Keep an empty path and an empty result.
Define backtrack(i): if i equals the length of digits, save a copy of path and return.
Otherwise, for each letter on the key of digits[i], in order: append it to path, call backtrack(i+1), then remove it.
Call backtrack(0) and return result.

KEYPAD = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
          "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}


def letterCombinations(digits):
    result = []
    path = []  # the letters chosen so far, one per digit

    def backtrack(i):
        if i == len(digits):
            # Every digit has a letter: this leaf is one finished string.
            result.append("".join(path))
            return
        for letter in KEYPAD[digits[i]]:
            path.append(letter)   # choose
            backtrack(i + 1)      # explore the digits after this one
            path.pop()            # undo, so the next letter can take its place

    backtrack(0)
    return result

Pitfalls and edge cases

Assuming every key has three letters. Taking three letters from index (d-2)*3 of the alphabet drops the s from 7 and starts 8 on s. Write the keypad out as a table.
Forgetting the undo. path keeps growing, and the second answer for "23" comes out as ade instead of ae.
Saving the buffer instead of a copy. In Python, result.append(path) stores the same list nine times, and by the end it is empty.
Trying a key's letters from right to left, or growing strings from a stack in the iterative version. Either breaks the sorted order.
In PHP and R, "23" may arrive as the number 23. Turn it into text before you index its characters.

Frequently asked questions3

What is the time complexity of Letter Combinations of a Phone Number?

O(4^n · n) for n digits: there can be 4^n strings, when every digit is 7 or 9, and each takes n steps to write. That is the size of the output, so no solution does better. Backtracking needs O(n) extra space besides the output.

Why does backtracking return the combinations in sorted order?

All answers have the same length, and a depth first walk finishes every string that starts with a before it chooses b. The same holds at every level, as long as each key's letters are tried from left to right. That is dictionary order, so no sort is needed.

What about the digits 0 and 1?

On a phone keypad, 0 and 1 carry no letters, and this version only uses 2 to 9. If they could appear, you would have to decide whether such a digit is skipped or makes the answer empty. In an interview, ask which one is wanted.

def letterCombinations(digits):
    # Write code here

Test #1

Test #2

Test #3

Argument

digits = "23"

Expected Output

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