Letter Combinations of a Phone Number

Difficulty: Medium Source: NeetCode

Problem

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digits to letters (just like on a telephone keypad) is given below. Note that 1 does not map to any letters.

2 → abc    3 → def    4 → ghi    5 → jkl
6 → mno    7 → pqrs   8 → tuv    9 → wxyz

Example 1: Input: digits = "23" Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2: Input: digits = "" Output: []

Example 3: Input: digits = "2" Output: ["a","b","c"]

Constraints:

• 0 <= digits.length <= 4
• digits[i] is a digit in the range ['2', '9'].

Prerequisites

Before attempting this problem, you should be comfortable with:

• Backtracking — at each step, branch on each letter mapped to the current digit
• Recursion — processing digits one at a time and combining results

1. Brute Force (Iterative)

Intuition

Start with a list containing one empty string. For each digit in digits, take every combination built so far and extend it with each letter that the current digit maps to. After processing all digits, the list contains all valid combinations. This is an iterative version of the backtracking idea.

Algorithm

1. Initialize result = [""].
2. For each digit in digits:
   • Get its letters from the phone map.
   • Replace result with every existing string in result extended by each letter.
3. Return result (or [] if digits is empty).

Solution

def letterCombinations_iterative(digits):
    if not digits:
        return []

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

    result = [""]
    for digit in digits:
        letters = phone_map[digit]
        result = [combo + letter for combo in result for letter in letters]
    return result


print(letterCombinations_iterative("23"))
# ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']
print(letterCombinations_iterative(""))
# []
print(letterCombinations_iterative("2"))
# ['a', 'b', 'c']

Complexity

• Time: O(4^n * n) — at most 4 letters per digit, n digits; building each string costs O(n)
• Space: O(4^n * n) — storing all combinations

2. Backtracking

Intuition

Process one digit at a time. For the digit at position index, try each letter it maps to, add that letter to the current combination, then recurse on index + 1. When index reaches the end of digits, the current combination is complete — add it to results. Each recursive call handles exactly one digit, so the recursion depth equals the number of digits.

Algorithm

1. Return [] if digits is empty.
2. Define the phone keypad mapping.
3. Define backtrack(index, current).
4. If index == len(digits): append "".join(current) to results and return.
5. For each letter in phone_map[digits[index]]:
   • Append letter, recurse with index + 1, pop letter.

Solution

def letterCombinations(digits):
    if not digits:
        return []

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

    result = []

    def backtrack(index, current):
        if index == len(digits):
            result.append("".join(current))
            return
        for letter in phone_map[digits[index]]:
            current.append(letter)
            backtrack(index + 1, current)
            current.pop()

    backtrack(0, [])
    return result


print(letterCombinations("23"))
# ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']
print(letterCombinations(""))
# []
print(letterCombinations("2"))
# ['a', 'b', 'c']
print(letterCombinations("79"))
# ['pw', 'px', 'py', 'pz', 'qw', 'qx', 'qy', 'qz', 'rw', 'rx', 'ry', 'rz', 'sw', 'sx', 'sy', 'sz']

Complexity

• Time: O(4^n * n) — at most 4 letters per digit; n digits; joining each combination costs O(n)
• Space: O(n) — recursion depth equals number of digits

Common Pitfalls

Not handling the empty string input. If digits = "", you should return [], not [""]. Always add this guard at the start.

Building the string with + vs. a list. In Python, string concatenation (current + letter) creates a new string object each time. Using a list and "".join(current) at the end is more efficient, especially for longer digit strings.

Forgetting to pop after the recursive call. If you’re using a mutable list current, you must current.pop() after each recursive call. Alternatively, pass an immutable string (current + letter) and skip the pop — this is simpler but slightly less efficient.