Letter Combinations of a Phone Number

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

It is 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. With only three-letter keys it is O(3^n · n) . No solution can do better, because that is the size of the output. 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. For "23" that is nine strings, from "ad" to "cf".

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, so there are 3 × 3 = 9 strings, and listing them with the first letter changing slowest keeps them sorted.

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.

+14 hidden tests on Submit

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

Nothing here can be skipped: the answer itself holds up to 4^n strings, so every correct solution spends at least that much work writing them. What the problem tests is whether you can generate a set of choices systematically, without missing or repeating one. That is backtracking in its plainest form: a decision tree with one level per digit, walked depth first, where every leaf is an answer.

Build the strings one digit at a time

Intuition

Build the answers one digit at a time. Start with a list that holds one empty string. For "23", the digit 2 turns it into a, b, c. The digit 3 then grows each of those three by d, e and f, which gives nine strings of length 2. After the last digit, the list holds every answer.

The order comes out sorted for free. Suppose the list is sorted before a digit. You extend the prefixes in that same order, and each prefix by the key's letters from left to right. A string with an earlier prefix still comes first, and two strings with the same prefix are ordered by the new letter, which is dictionary order.

The cost is the size of the answer. With n digits the last list has up to 4^n strings of length n, and all the earlier lists together hold at most half as many strings, all of them shorter. The drawback is memory: while you build a level, the whole previous level is held as well, including every short prefix you will throw away.

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

Think of the answer as a decision tree. The root is an empty string. For "23" it has three children, a, b and c, one for each letter of 2. Each of those has three children of its own, one for each letter of 3. The tree has one level per digit, and the nine leaves, ad through cf, are exactly the answers.

Backtracking walks that tree depth first with a single buffer, path. At level i you choose a letter of digits[i] by appending it, explore everything below it by recursing on i+1, and undo the choice by removing the letter. The undo is what lets one buffer serve the whole tree: after ad, ae and af are saved, popping returns path to a, then to the empty string, ready for b. When i equals the length of digits, the buffer is a full answer, and you save a copy of it.

Trying letters from left to right at every level visits the leaves in dictionary order, so the output needs no sort. In this problem every branch ends in an answer, so there is nothing to prune; the tree is only 4 levels deep and has at most 256 leaves. The work is still O(4^n · n) for writing the answers, but the extra memory is the buffer and the call stack, O(n), instead of a whole level of prefixes. The same choose, explore, undo loop solves subsets, permutations, combination sum and word search.

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

The search itself is short, so most bugs come from the keypad or from the shared buffer.

Assuming every key has three letters. 7 is pqrs and 9 is wxyz, so taking three letters from index (d-2)*3 of the alphabet drops the s from 7 and starts 8 on s instead of t. Write the keypad out as a table.
Forgetting the undo. Without removing the letter after the recursive call, 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. Join it into a new string when you save it.
Losing the order. Trying a key's letters from right to left, or growing the strings from a stack in the iterative version, gives the answers in a different order than the sorted one the problem asks for.
A digit string read as a number. In loosely typed languages such as PHP and R, "23" may reach you as the number 23. Turn it into text before you index its characters.

Frequently asked questions4

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

It is 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. With only three-letter keys it is O(3^n · n). No solution can do better, because that is the size of the output. Backtracking needs O(n) extra space besides the output.

Can you solve Letter Combinations without recursion?

Yes. Build the answers level by level: start from one empty string and, for each digit, extend every string you have by every letter of that key. It does the same amount of work, and it is the same tree walked breadth first instead of depth first. It holds a whole level of prefixes in memory, while recursion only needs a stack as deep as the number of digits.

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 at the first level. The same holds at every level, as long as each key's letters are tried from left to right. That is exactly 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 of the problem 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, since it offers no letter to choose. In an interview, ask which one is wanted before you code it.

Python

def letterCombinations(digits):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

digits = "23"

Expected

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