MediumBacktrackingRecursionString

Letter Combinations of a Phone Number

1 approach, code in every language

Given a string of digits between 2 and 9, imagine the classic telephone keypad where each of those digits maps to a small group of letters. Produce every possible string of letters that could be typed by pressing the given digits in order, choosing one letter per digit.

Return all such combinations in any order. If the input string is empty, there are no letters to choose and the answer is an empty list.

Example 1

Input: digits = "23"

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

Digit two offers a, b, c and digit three offers d, e, f, so every pairing is produced.

Example 2

Input: digits = ""

Output: []

No digits means there is nothing to combine.

Constraints

0 <= digits.length <= 4
Each character in digits is a digit from 2 through 9
No two returned combinations are identical

Digit-by-digit backtracking

Walk through the digits left to right, and for each digit append every letter it maps to, recursing until a full-length combination is formed.

Loading animation…

Intuition

Each digit contributes exactly one letter to a combination, and the choices for one digit are independent of the choices for the others. This is a Cartesian product, which backtracking builds naturally: fix the letter for the current digit, move on to the next digit, and when we have chosen a letter for every digit the combination is complete. Undoing the last chosen letter lets us cycle through the remaining letters of the current digit.

Algorithm walkthrough

1Return an empty list immediately when the input has no digits.
2Keep a mapping from each digit character to its group of letters.
3Recurse with an index into digits and the letters chosen so far.
4When the index reaches the end of digits, store the assembled string.
5Otherwise, for each letter of the current digit, append it, recurse to the next index, then remove it.

Implementation

class Solution:
    def letterCombinations(self, digits: str) -> list[str]:
        if not digits:
            return []
        mapping = {
            "2": "abc", "3": "def", "4": "ghi", "5": "jkl",
            "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz",
        }
        result = []

        def backtrack(index: int, path: str) -> None:
            if index == len(digits):
                result.append(path)
                return
            for letter in mapping[digits[index]]:
                backtrack(index + 1, path + letter)

        backtrack(0, "")
        return result

Time

O(4^n * n)

Space

O(n)

n is the number of digits; some digits map to four letters, and copying each finished string costs O(n).

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Recursion

After the pattern

Now solve one you haven't seen.

Keypad Code Spellings is our own problem on the technique behind Letter Combinations of a Phone Number: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free