Letter Combinations of a Phone Number

You are given a string digits made up of digits from 2 through 9 inclusive.

Each digit (not including 1) is mapped to a set of characters exactly like on a traditional telephone keypad.

Return all possible letter combinations that the number could represent. You may return the answer in any order.

Examples

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

Prerequisites

Before attempting this problem, you should be comfortable with:

• Recursion - Understanding recursive calls and building results through multiple levels.
• Backtracking - Exploring all branches of a decision tree and building combinations step by step.
• Hash Maps/Dictionaries - Mapping keys (digits) to values (corresponding letters).

1. Backtracking

Intuition

Each digit maps to a set of characters (like on a phone keypad). The task is to choose one character per digit, in order, and generate all possible combinations.

Think of it as building a string step by step:

• At index i, pick one character from the mapping of digits[i].
• Move to the next digit.
• When the length of the built string equals the number of digits, we have formed one valid combination.

This is a classic decision tree problem where each level is a digit, and each branch is a possible character for that digit. Backtracking lets us explore all branches efficiently.

If the input string is empty, return an empty list.

Create a mapping from digits (2-9) to their corresponding letters.

Use a recursive function backtrack(index, currentString):
  If currentString length equals the number of digits:
    Add it to the result
    Return
    
  For each character mapped from digits[index]:
    Append the character to currentString
    Recurse to the next index: backtrack(index + 1, currentString)
    (Backtrack by removing the character is handled via string immutability in Python, or explicitly in Java)

Start backtracking from index 0 with an empty string.
Return all collected combinations.

2. Iteration (Level-order Expansion)

Intuition

Instead of using recursion, we can build combinations level by level. Start with an empty string. For each digit, take all combinations built so far, and append every possible character mapped to the current digit. This creates a new list of combinations. This is similar to a BFS or level-wise expansion.

If the input string is empty, return an empty list.

Initialize the result list with one empty string: [""].
Create a digit-to-characters mapping.

For each digit in the input:
  Create a temporary list
  For every existing string in the result list:
    Append each possible character of the current digit
    Store the new strings in the temporary list
  Replace the result list with the temporary list

Return the result list.

Time Complexity: O(N * 4^N) where N is the length of digits. The max number of branches per digit is 4.

Space Complexity: O(N * 4^N) for the output array.

Common Pitfalls

Not Handling Empty Input

When digits is empty, returning [""] (a list with an empty string) is wrong. The correct answer is [] (an empty list) since there are no combinations to form.

# Wrong: returns list with empty string if not digits: return [""] # Correct: return empty list if not digits: return []

Incorrect Digit-to-Letter Mapping

Digit 7 maps to "pqrs" (4 letters) and digit 9 maps to "wxyz" (4 letters), not 3 letters each. Using "qprs" instead of "pqrs" for digit 7 produces wrong orderings.

Off-by-One in Digit Indexing

When using an array for digit mapping in Java, indices 0 and 1 have no letters. Forgetting this offset or incorrectly computing digit - '0' leads to index errors or wrong character mappings.

// digitToChar[0] and digitToChar[1] should be empty String[] digitToChar = {"", "", "abc", "def", ...}; // Access with: String letters = digitToChar[digit - '0'];