1. Problem Formulation & The ITU E.161 Telephony Mapping

The standard telephone keypad mapping establishes the following relationship between numeric digits and alphabetic characters:

• 2 → "abc", 3 → "def", 4 → "ghi"
• 5 → "jkl", 6 → "mno", 7 → "pqrs"
• 8 → "tuv", 9 → "wxyz"
• Digits 0 and 1 map to no letters and are excluded from valid inputs.

Given an input string such as "23", our goal is to construct the Cartesian product of the corresponding character sets: {a, b, c} × {d, e, f}, yielding 9 combinations: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

2. Algorithmic Paradigms: Recursive Backtracking (DFS) vs. Iterative Queue (BFS)

There are two distinct computational approaches to generating the full combinatorial state space:

Approach A: Depth-First Search with Backtracking

In DFS backtracking, we maintain a mutable string buffer representing our current exploration path. At each recursive depth index:

1. If index == digits.length, our path contains a complete combination; we clone the buffer into our final results array and backtrack.
2. Otherwise, retrieve the candidate characters for digits[index].
3. Iterate through each letter: append the letter to the path buffer, recursively invoke backtrack(index + 1), and upon return, pop the letter off the buffer to restore state for the next sibling branch.

By reusing a single mutable buffer (e.g., std::string in C++, StringBuilder in Java, or an array of characters in TypeScript), we avoid generating thousands of temporary garbage strings during the traversal.

Approach B: Breadth-First Iterative Queue (BFS)

BFS builds combinations iteratively level by level without recursion. Starting with a queue containing a single empty string [""], for each incoming digit, we dequeue all existing prefix strings, append each candidate letter corresponding to the digit, and enqueue the newly formed strings back into the queue. While intuitive, BFS stores all partial combinations in memory simultaneously, demanding greater transient memory than DFS.

3. Production-Grade Implementations

Below are idiomatic, high-performance implementations in TypeScript, C++20, and Python 3.

TypeScript Implementation

/**
 * LeetCode 17: Letter Combinations of a Phone Number
 * Time: O(3^N * 4^M) | Space: O(N + M) auxiliary recursion depth
 */
export function letterCombinations(digits: string): string[] {
  if (digits.length === 0) {
    return [];
  }

  // Pre-allocated digit-to-letter mappings
  const digitMap: Record = {
    '2': ['a', 'b', 'c'],
    '3': ['d', 'e', 'f'],
    '4': ['g', 'h', 'i'],
    '5': ['j', 'k', 'l'],
    '6': ['m', 'n', 'o'],
    '7': ['p', 'q', 'r', 's'],
    '8': ['t', 'u', 'v'],
    '9': ['w', 'x', 'y', 'z']
  };

  const results: string[] = [];
  const currentPath: string[] = [];

  function backtrack(index: number): void {
    // Base Case: Path reached required combination length
    if (index === digits.length) {
      results.push(currentPath.join(''));
      return;
    }

    const letters = digitMap[digits[index]];
    if (!letters) return;

    for (let i = 0; i < letters.length; i++) {
      currentPath.push(letters[i]);   // Choose
      backtrack(index + 1);          // Explore
      currentPath.pop();             // Un-choose (Backtrack)
    }
  }

  backtrack(0);
  return results;
}

Modern C++20 Implementation

#include <iostream>
#include <vector>
#include <string>
#include <string_view>
#include <array>

class Solution {
private:
    static constexpr std::array<std::string_view, 10> DIGIT_MAP = {
        "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
    };

    void backtrack(std::string_view digits, size_t index, std::string& current, std::vector<std::string>& results) {
        if (index == digits.size()) {
            results.push_back(current);
            return;
        }

        int digit = digits[index] - '0';
        std::string_view letters = DIGIT_MAP[digit];

        for (char c : letters) {
            current.push_back(c);                 // Push
            backtrack(digits, index + 1, current, results); // Recurse
            current.pop_back();                  // Pop
        }
    }

public:
    std::vector<std::string> letterCombinations(std::string digits) {
        if (digits.empty()) return {};

        std::vector<std::string> results;
        std::string current;
        current.reserve(digits.size());

        backtrack(digits, 0, current, results);
        return results;
    }
};

Python 3 Implementation

from typing import List

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []

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

        results = []
        path = []

        def backtrack(index: int):
            if index == len(digits):
                results.append("".join(path))
                return

            for char in digit_map[digits[index]]:
                path.append(char)
                backtrack(index + 1)
                path.pop()

        backtrack(0)
        return results

4. Rigorous Asymptotic Complexity Analysis

• Combinatorial Output Bound: Let $N$ be the number of input digits mapping to 3 letters (digits 2, 3, 4, 5, 6, 8) and $M$ be the number of digits mapping to 4 letters (digits 7, 9). The total number of valid leaf combinations generated is exactly $3^N imes 4^M$.
• Time Complexity: O(3^N × 4^M × (N + M)): In a decision tree, the number of leaf nodes dominates runtime. For each of the $3^N imes 4^M$ combinations, constructing and copying the final string of length $L = N + M$ takes $O(L)$ time. Hence, the overall time complexity is bounded by $O(3^N imes 4^M imes L)$.
• Auxiliary Space Complexity: O(N + M): The recursion call stack reaches a maximum depth equal to the length of the input string $L = N + M$. The mutable path buffer similarly consumes $O(L)$ space. (Note: The output array containing $3^N imes 4^M$ strings of length $L$ requires $O(3^N imes 4^M imes L)$ space, which is dictated by the problem's output requirements).

5. Real-World Applications: T9 Predictive Text & Telephone Word Search

The combinatorial explosion of raw Cartesian products illustrates why early mobile engineers could not simply present every raw permutation to users. For an eight-digit phone number, generating $3^8 = 6,561$ permutations on a 16MHz mobile CPU overwhelmed memory buffers.

To solve this, Tegic Communications invented T9 (Text on 9 keys) in 1995. Rather than generating every Cartesian product, T9 cross-referenced the user's keystroke sequence against a compacted Prefix Trie (radix tree) containing real dictionary words. Branches that failed to form valid word prefixes were pruned instantly, allowing mobile devices to resolve ambiguous keystrokes in sub-millisecond real time.