Problem Description

You are given a string containing digits from 2 to 9 inclusive. Your task is to return all possible letter combinations that the number could represent, similar to how letters are mapped on a telephone keypad.

The digit-to-letter mapping follows the traditional phone keypad layout:

• 2 maps to "abc"
• 3 maps to "def"
• 4 maps to "ghi"
• 5 maps to "jkl"
• 6 maps to "mno"
• 7 maps to "pqrs"
• 8 maps to "tuv"
• 9 maps to "wxyz"

Note that the digit 1 does not map to any letters.

For example:

• If the input is "23", you need to combine all letters from digit 2 ("abc") with all letters from digit 3 ("def"), resulting in ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
• If the input is an empty string, return an empty list [].

The answer can be returned in any order.

The solution uses an iterative approach where it processes each digit one by one. Starting with an initial list containing an empty string, it iterates through each digit in the input. For each digit, it looks up the corresponding letters and creates new combinations by appending each letter to all existing combinations. The process continues until all digits have been processed, building up the complete set of letter combinations.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• No: The problem does not involve nodes and edges or graph traversal. We're dealing with generating combinations from digit-to-letter mappings.

Need to solve for kth smallest/largest?

• No: We're not looking for the kth smallest or largest element. We need to generate all possible combinations.

Involves Linked Lists?

• No: The problem doesn't involve linked list data structures or operations.

Does the problem have small constraints?

• Yes: The input string contains digits from 2-9, and phone numbers typically have a limited length (the problem constraints usually limit the string length to 4 or less). Each digit maps to at most 4 letters, making the total number of combinations manageable.

Brute force / Backtracking?

• Yes: We need to explore all possible letter combinations systematically. For each digit, we must try every possible letter it maps to and combine it with all possible combinations from the remaining digits. This is a classic backtracking scenario where we build combinations incrementally and explore all paths.

Conclusion: The flowchart suggests using a Backtracking approach for generating all letter combinations. This makes sense because we need to:

1. Make a choice (pick a letter for the current digit)
2. Explore further (move to the next digit)
3. Backtrack if needed (try the next letter for the current digit)
4. Generate all valid combinations by exploring all possible paths

Intuition

Think about how you would manually write down all possible combinations for a phone number like "23". You'd likely start with the first digit 2 which maps to "abc", and for each letter (a, b, c), you'd combine it with each letter from the second digit 3 which maps to "def" (d, e, f).

This naturally forms a tree-like structure where each level represents a digit, and each branch represents choosing a specific letter for that digit. The root starts empty, and as we go deeper, we build up our combinations letter by letter.

The key insight is that we need to explore every possible path from root to leaf in this decision tree. This is where backtracking shines - it's perfect for systematically exploring all paths in a tree structure.

However, the given solution takes a clever iterative approach instead of traditional recursive backtracking. It builds combinations level by level, similar to breadth-first traversal. Starting with [""] (an empty combination), for each digit encountered:

1. Take all existing partial combinations
2. For each partial combination, append each possible letter from the current digit
3. These new combinations become the foundation for the next digit

For example, with "23":

• Start: [""]
• Process 2 ("abc"): ["a", "b", "c"]
• Process 3 ("def"): ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

This approach elegantly avoids explicit backtracking by maintaining all valid partial solutions at each step and systematically extending them. It's like building a Cartesian product incrementally - for each new digit, we multiply our existing combinations by the number of letters that digit represents.

The beauty of this solution is its simplicity: the list comprehension [a + b for a in ans for b in s] captures the essence of combining every existing partial solution with every new letter possibility, effectively exploring all branches of our decision tree in just one line.

Learn more about Backtracking patterns.

Solution Approach

The solution uses an iterative traversal approach to build all letter combinations progressively. Let's walk through the implementation step by step:

1. Handle Edge Case:

if not digits:
    return []

If the input string is empty, return an empty list immediately since there are no combinations to generate.

2. Set Up the Digit-to-Letter Mapping:

d = ["abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]

Create an array where index i corresponds to digit i+2. For example:

• d[0] = "abc" corresponds to digit 2
• d[1] = "def" corresponds to digit 3
• And so on...

3. Initialize the Result:

ans = [""]

Start with a list containing one empty string. This serves as the base for building combinations - we'll append letters to this empty string as we process each digit.

4. Process Each Digit Iteratively:

for i in digits:
    s = d[int(i) - 2]
    ans = [a + b for a in ans for b in s]

For each digit in the input string:

• Convert the digit character to an integer and subtract 2 to get the correct index in our mapping array
• Retrieve the corresponding letters (e.g., for digit '2', get "abc")
• Use a nested list comprehension to create all new combinations:
  • For each existing combination a in ans
  • For each letter b in the current digit's letters s
  • Create a new combination by concatenating a + b

Example Walkthrough for "23":

Initial state: ans = [""]

Processing digit '2' (letters: "abc"):

• Combine "" with 'a' → "a"
• Combine "" with 'b' → "b"
• Combine "" with 'c' → "c"
• Result: ans = ["a", "b", "c"]

Processing digit '3' (letters: "def"):

• Combine "a" with each of "def" → ["ad", "ae", "af"]
• Combine "b" with each of "def" → ["bd", "be", "bf"]
• Combine "c" with each of "def" → ["cd", "ce", "cf"]
• Result: ans = ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

Time Complexity: O(4^n × n) where n is the length of the input string. In the worst case, each digit maps to 4 letters (like digit 7 or 9), giving us 4^n combinations, and each combination has length n.

Space Complexity: O(4^n × n) to store all the generated combinations in the result list.

This iterative approach elegantly avoids recursion and explicit backtracking by maintaining all valid partial solutions at each step and systematically extending them with new letters.

Example Walkthrough

Let's walk through the solution with input "23" to see how the iterative approach builds combinations step by step.

Initial Setup:

• Input: "23"
• Mapping: d = ["abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
• Start with: ans = [""] (list with one empty string)

Step 1: Process digit '2'

• Digit '2' maps to index 2-2 = 0 in our array
• Letters for '2': s = "abc"
• Apply list comprehension: [a + b for a in ans for b in s]
  • Take "" from ans, append 'a' → "a"
  • Take "" from ans, append 'b' → "b"
  • Take "" from ans, append 'c' → "c"
• New ans = ["a", "b", "c"]

Step 2: Process digit '3'

• Digit '3' maps to index 3-2 = 1 in our array
• Letters for '3': s = "def"
• Apply list comprehension: [a + b for a in ans for b in s]
  • Take "a" from ans:
    • Append 'd' → "ad"
    • Append 'e' → "ae"
    • Append 'f' → "af"
  • Take "b" from ans:
    • Append 'd' → "bd"
    • Append 'e' → "be"
    • Append 'f' → "bf"
  • Take "c" from ans:
    • Append 'd' → "cd"
    • Append 'e' → "ce"
    • Append 'f' → "cf"
• Final ans = ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

Visualization of Growth:

Start:        [""]           (1 combination of length 0)
After '2':    ["a", "b", "c"]  (3 combinations of length 1)
After '3':    ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]  (9 combinations of length 2)

Notice how the number of combinations multiplies: we had 3 partial combinations after processing '2', and since '3' has 3 letters, we end up with 3 × 3 = 9 total combinations. Each iteration extends all existing combinations with every possible letter from the current digit.

Solution Implementation

Time and Space Complexity

The time complexity is O(4^n), where n is the length of the input digits string.

Time Complexity Analysis:

• Each digit maps to at most 4 letters (digits 7 and 9 map to "pqrs" and "wxyz" respectively)
• For each digit in the input, we iterate through all existing combinations and append each possible letter
• If we have n digits, and each digit can map to at most 4 letters, the total number of combinations generated is at most 4^n
• For each combination, we perform string concatenation operations
• Therefore, the overall time complexity is O(4^n)

The space complexity is O(4^n), where n is the length of the input digits string.

Space Complexity Analysis:

• The ans list stores all possible letter combinations
• In the worst case (when all digits map to 4 letters), we generate 4^n combinations
• Each combination has length n, so technically the total space used is O(n * 4^n)
• However, since we're counting the number of combinations as the primary factor, the space complexity is considered O(4^n)
• The intermediate lists created during list comprehension also contribute to space usage, but don't exceed the final result size
• Therefore, the overall space complexity is O(4^n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Digit-to-Index Mapping

One of the most common mistakes is incorrectly mapping digits to their corresponding letter groups. Since digits start from 2 (not 0), you need to subtract 2 from the digit to get the correct array index.

Incorrect:

# Wrong: Using digit directly as index
letters = digit_to_letters[int(digit)]  # This would cause IndexError

# Wrong: Subtracting 1 instead of 2
letters = digit_to_letters[int(digit) - 1]  # Maps 2→"def", 3→"ghi" (off by one)

Correct:

letters = digit_to_letters[int(digit) - 2]  # Maps 2→"abc", 3→"def" correctly

2. Forgetting to Handle Empty Input

Without checking for empty input, the function would return [""] instead of [], which is incorrect according to the problem specification.

Incorrect:

def letterCombinations(self, digits: str) -> List[str]:
    digit_to_letters = ["abc", "def", ...]
    result = [""]
    for digit in digits:  # Empty string would skip loop
        # ...
    return result  # Returns [""] for empty input, should be []

Correct:

def letterCombinations(self, digits: str) -> List[str]:
    if not digits:
        return []  # Explicitly handle empty input
    # ... rest of the code

3. Overwriting Result List During Iteration

A subtle bug can occur if you try to modify the result list while iterating over it in the wrong way.

Incorrect:

# This approach modifies result in place incorrectly
result = [""]
for digit in digits:
    letters = digit_to_letters[int(digit) - 2]
    new_result = []
    for existing in result:
        for letter in letters:
            new_result.append(existing + letter)
    result = new_result  # Reassigning is fine, but...
  
# Or worse, trying to modify in place:
for digit in digits:
    letters = digit_to_letters[int(digit) - 2]
    for i in range(len(result)):  # Dangerous if result changes size
        for letter in letters:
            result.append(result[i] + letter)  # This causes infinite loop!

Correct:

# Create a completely new list each iteration
result = [""]
for digit in digits:
    letters = digit_to_letters[int(digit) - 2]
    result = [existing + letter 
             for existing in result 
             for letter in letters]

4. Memory Inefficiency with Large Inputs

While not exactly a bug, the iterative approach stores all intermediate results, which can be memory-intensive. For very long digit strings, consider using a generator or recursive approach with yield to produce results on-demand rather than storing everything at once.

Alternative approach for memory efficiency:

def letterCombinations(self, digits: str):
    if not digits:
        return []
  
    digit_to_letters = ["abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
  
    def backtrack(index, path):
        if index == len(digits):
            result.append(path)
            return
      
        letters = digit_to_letters[int(digits[index]) - 2]
        for letter in letters:
            backtrack(index + 1, path + letter)
  
    result = []
    backtrack(0, "")
    return result

This recursive approach uses the call stack instead of maintaining all intermediate combinations, which can be more memory-efficient for certain use cases.