Skip to main content
DSA patterns

Letter Combinations of a Phone Number

mediumRecursion Must-do

Problem statement

You are given a string of digits, each one between 2 and 9. Each digit stands for a set of letters, the same letters printed on an old phone keypad: 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. The digits 0 and 1 have no letters, so the input never contains them.

Return every string you can build by picking exactly one letter for each digit, in the same order the digits appear. The strings can come back in any order. If the input is empty, return an empty list.

image

Examples

Example 1

Input: digits = "23"

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

Explanation: 2 maps to a, b, c and 3 maps to d, e, f. Pairing each letter of the first digit with each letter of the second gives 3 x 3 = 9 strings.

Example 2

Input: digits = "2"

Output: ["a","b","c"]

Explanation: With only one digit, the answer is just that digit's three letters, each as a one-letter string.

Example 3

Input: digits = ""

Output: []

Explanation: There are no digits to turn into letters, so the answer is an empty list, not a list that holds one empty string.

Hints

Hint 1: Start smaller. If the input had only one digit, ask yourself what you would return.

Approach

Optimal: Iterative build-up

Intuition

Instead of going deep first (one full combination before the next), grow the whole set of combinations one digit at a time. Start with a list holding only the empty string. For each digit, take every combination built so far and extend it with every letter of that digit. That replaces the list with a longer one. After the last digit, the list holds every combination. It gives the same result as backtracking, built breadth-first instead of depth-first, and it needs no recursion.

Steps

  1. If digits is empty, return an empty list.
  2. Start a list that holds one entry: the empty string.
  3. For each digit, build a new list: for every string in the current list, add one new string per letter of that digit.
  4. Replace the old list with the new one and move to the next digit.
  5. After the last digit, the list holds every valid combination.

Dry run

digits = "23"

after digit list
start [""]
2 ["a", "b", "c"]
3 ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

Edge cases: an empty digits must return []. The check happens before the loop. Without it the list would stay [""], which is the wrong answer.

Complexity

Time O(n · 4ⁿ) - The total work matches backtracking. At each of the n digits, every existing string is extended by every letter of that digit, so the list can grow up to four times larger at each step. Copying a string of length up to n for each new entry gives the extra factor of n.

Space O(4ⁿ) - Unlike backtracking, this approach keeps the whole current list of partial combinations in memory, not just one in-progress string. That list is also the final answer at the end, but it is held in full at every step before it.

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",
        }
        combinations = [""]
        for digit in digits:
            combinations = [
                combo + letter
                for combo in combinations
                for letter in mapping[digit]
            ]
        return combinations


if __name__ == "__main__":
    import json

    print(json.dumps(Solution().letterCombinations("23"), separators=(",", ":")))
    print(json.dumps(Solution().letterCombinations("2"), separators=(",", ":")))
    print(json.dumps(Solution().letterCombinations(""), separators=(",", ":")))
RecapThe whole problem in a few lines, for the night before
  • Spot it: build every combination by choosing one option per position, from a small fixed lookup table
  • Idea: backtrack one digit at a time: add a letter, recurse into the next digit, remove the letter, try the next one
  • Cost: O(n · 4ⁿ) time either way; O(n) extra space for backtracking and O(4ⁿ) for the iterative build-up
  • Trap: empty digits must return [], not [""]

Interview follow-ups

  • What if you only need the number of combinations, not the strings?

    You do not need to build anything. Multiply together the number of letters each digit maps to: 3 for most digits and 4 for 7 and 9. That is O(n) time and O(1) space, against O(n · 4ⁿ) time and O(4ⁿ) space to build and count the list. Return 0 for an empty input.

  • What if digits could be up to length 20 instead of 4?

    4²⁰ is over a trillion, so returning the full list is no longer realistic, and memory would run out long before you finish. Turn the backtracking function into a generator (yield in Python, or a callback in Java and C++) that produces one combination at a time. Memory drops back to O(n), because you never hold more than one in-progress path plus whatever the caller does with each combination as it arrives.

  • What if a digit could map to zero letters, for example a broken key?

    Check the letter set for that digit before looping. If it is empty, the current branch cannot be completed with a letter at that position. Depending on what the interviewer wants, either skip that digit's contribution, or treat the whole input as having no valid combination. Ask which behaviour is intended before you code either one.

Frequently asked questions

Each digit is a branch point with up to 4 choices, so the whole search space forms a tree even though nothing is drawn as a graph. Walking that tree depth-first, one digit per level, is exactly what the recursive backtracking approach does. That is why the problem sits with other tree-shaped recursion problems rather than with graph traversal.

On the physical phone keypad these two keys never had letters printed on them. Only 2 to 9 do. The problem keeps that rule, so your code never has to handle a digit with an empty letter set.

Generating every combination from a few independent choices comes up whenever you build candidates from a template. Examples are building every hostname from short lists of environment and region codes, or listing every combination of feature-flag values to test. The core idea is the same: pick one option per position and combine them.

They do the same total work, so neither is faster in Big-O terms. Backtracking is usually preferred because it holds only one in-progress string at a time plus the final output. The iterative version keeps a full, growing list at every step. The iterative one avoids recursion limits, which hardly matter here because the input is at most 4 digits.

Returning [""] instead of [] for an empty digits string. The recursive base case technically succeeds with an empty path, so the bug is easy to miss. The fix is an explicit empty check before doing anything else.