Start learning free

LESSON 356 OF 569 · BACKTRACKING

Letter Combinations of a Phone Number in Python: Backtracking

Practice O(n · 4n) Read the full explanation

Given a string digits made of the digits 2 to 9, return every letter combination the number could spell on a phone keypad.

Each digit stands for the letters on its key:

2: a b c      3: d e f      4: g h i
5: j k l      6: m n o      7: p q r s
8: t u v      9: w x y z

A combination takes one letter from each digit's key, in the order of the digits. Return the combinations in keypad order: every combination that starts with the first letter of the first digit's key comes before every combination that starts with its second letter, and so on; inside each of those groups, the same rule for the second digit, then the third. (Each key's letters are in alphabetical order, so this is also alphabetical order.)

If digits is empty, there is nothing to spell: return no combinations at all, not one empty string.

 

Example 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Explanation: 2 gives a, b or c, and 3 gives d, e or f: 3 × 3 = 9 combinations.
The three that start with a come first, in the order of 3's letters; then the ones that start with b, then c.

Example 2:

Input: digits = ""
Output: []
Explanation: No digits, so there are no combinations.

Example 3:

Input: digits = "7"
Output: ["p","q","r","s"]
Explanation: With one digit, each letter of its key is a combination. The keys 7 and 9 have four letters, the others three.

 

Constraints:

  • 0 <= digits.length <= 4
  • Each character of digits is a digit from '2' to '9'.

Note:

The tutorial uses backtracking. Walk through digits one position at a time, keeping the letters chosen so far in a string current. At position i, try each letter of the key of digits[i], in the key's order: add it to the end of current and go on to position i + 1. When the position reaches the end of digits, every digit has its letter: save current. Trying the letters in the key's order gives exactly the keypad order above. Each call gets its own longer string, so nothing has to be undone when a call returns.

Each key has at most 4 letters, so n digits give at most 4n combinations, and building one takes n steps: the time is O(n · 4n). Besides the answer, the search keeps at most O(n) calls open at a time, one per digit (their strings add up to O(n2) characters at most).

STEP 1 OF 11
    Ctrl + Enter to check

    PYTHON · BACKTRACKING

    Letter Combinations Of A Phone Number in Python, explained

    Problem overview

    The function letterCombinations receives digits, a string of characters from '2' to '9', and returns every string those digits could spell on a phone keypad. Each digit stands for the letters on its key: 2 for abc, 3 for def, 4 for ghi, 5 for jkl, 6 for mno, 7 for pqrs, 8 for tuv and 9 for wxyz. A combination takes one letter from each digit's key, in the order of the digits.

    For "23" the answer is ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]: three letters for 2 times three for 3 makes nine combinations. They come in keypad order, so everything starting with a precedes everything starting with b, and inside each group the second letter follows the key's own order. For "7" the answer is ["p", "q", "r", "s"], and for the empty string it is an empty list, not a list holding an empty string.

    Approach: choose one letter per digit

    The number of letters in a combination depends on the number of digits, so you can't write a fixed number of nested loops. Backtracking handles any length. Walk through digits one position at a time, and keep the letters chosen so far in a string, current. At position i, try each letter of the key of digits[i], in the key's order. Add it to current and move on to position i + 1. When the position reaches the end of digits, every digit has its letter, so current is a full combination and is saved.

    Trying the letters in the key's order gives the keypad order for free. The call for the first digit tries a first and finishes everything that starts with a before it tries b.

    For "23", the helper is called 13 times in all: once for the empty start, three times for the letters of 2, and nine times for the pairs. The first calls, written as (position, letters so far), are:

    (0, '')
(1, 'a')
(2, 'ad')
(2, 'ae')
(2, 'af')
(1, 'b')

    Each call with position 2 is a finished combination. Once the call for 'a' has tried all three letters of 3, it returns, and the first call moves on to 'b'.

    There is no need to undo anything after a recursive call. In Python a string never changes, so current + letter builds a new string for the deeper call and leaves current as it was for the next letter. Backtracking with a list would need an explicit pop(); here the immutable string does that work.

    Step by step

    1. Create result, an empty list that will hold the combinations.
    2. Return early for empty input. If digits is empty, return result at once. Without this check the search would reach the end of the digits immediately and record the empty string as a combination.
    3. Build keypad, a list indexed by digit. Entries 0 and 1 are empty strings, because those keys have no letters. They are there so that every other key sits at its own index, and 0 and 1 never appear in the input.
    4. Start the search with self.backtrack(digits, 0, "", keypad, result): position 0, no letters chosen yet.
    5. Return result. The helper appends to this same list, so it holds every combination after the call.
    6. Declare the helper backtrack with the digits, the position i, current, the keypad and the result list.
    7. Test for the end. When i == len(digits), every digit has a letter.
    8. Save and stop. Append current to result and return. No copy is needed, since a string can't change afterwards.
    9. Look up the letters of this digit: int(digits[i]) turns a character such as "7" into the number 7, the index of its key.
    10. Loop over the letters in the key's order.
    11. Recurse with i + 1 and current + letter.

    The solution in Python

    class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        result = []
        if not digits:
            return result
        keypad = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
        self.backtrack(digits, 0, "", keypad, result)
        return result

    def backtrack(self, digits, i, current, keypad, result):
        if i == len(digits):
            result.append(current)
            return
        letters = keypad[int(digits[i])]
        for letter in letters:
            self.backtrack(digits, i + 1, current + letter, keypad, result)

    The Python details worth a closer look:

    • Strings are iterable. for letter in letters walks a string such as "pqrs" one character at a time, so the keypad can hold plain strings instead of lists of letters.
    • Indexing by digit. digits[i] is a one-character string, and a list can't be indexed with a string. The int(...) call is what makes keypad[int(digits[i])] work.
    • The result list is shared. Lists are passed by reference, so every recursive call appends to the one result created in letterCombinations. That is why the helper needs no return value.
    • Helper methods. backtrack is a method of the class, so it is called as self.backtrack(...) and its first parameter is self.

    Another way: itertools.product

    The standard library can build the same combinations. In a file of your own, with the same keypad list, this returns the same answers, in the same order, for "23" and "79":

    from itertools import product

def letter_combinations(digits):
    if not digits:
        return []
    keypad = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
    return ["".join(p) for p in product(*(keypad[int(d)] for d in digits))]

    It is shorter, but the backtracking version shows the structure that the harder problems of this chapter use.

    Complexity

    Time: O(n · 4^n). Each key has at most four letters, so n digits give at most 4^n combinations, and building each takes up to n steps for the string concatenations. With "7777" there are 256 combinations.

    Space: besides the answer, O(n). There is one active call per digit, and each holds a string of at most n letters.

    Edge cases and common mistakes

    • Empty input. "" must give []. Without the early return the same search returns [''], a list with one empty string.
    • One digit. "2" gives ["a", "b", "c"] and "7" gives four letters. Keys 7 and 9 have four letters, the others three.
    • Different key sizes. "79" gives 16 combinations and "92" gives 12. The count is the product of the key sizes, not a power of one number.
    • Forgetting int(). keypad["2"] raises a TypeError ("list indices must be integers or slices, not str").
    • Keypad without the two empty entries. If the list starts at "abc", every digit looks up the wrong key: digit 2 would find "ghi", and digit 9 would raise an IndexError.

    Testing

    • "23" gives ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
    • "" gives [].
    • "7" gives ["p", "q", "r", "s"].
    • "2" gives ["a", "b", "c"].
    • "92" gives ["wa", "wb", "wc", "xa", "xb", "xc", "ya", "yb", "yc", "za", "zb", "zc"].
    Keep going with Python500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free