Phone Number Mnemonics

Tags

Phone Number Mnemonics

Category

Recursion

Difficulty

Medium

Problem Statement

Given a string of digits (0-9) representing a phone number, return all possible letter combinations that the number could represent based on the traditional phone keypad mapping (e.g., 2 -> "abc", 3 -> "def", ..., 9 -> "wxyz"). Digits 0 and 1 map to themselves only.

Intuition

Each digit maps to a set of possible characters. To generate all combinations, we make a choice for the first digit, then recursively generate all combinations for the remaining digits. This is a classic backtracking problem where the branching factor at each level depends on how many letters the current digit maps to (3 or 4 typically).

Approach

  1. Define the phone keypad mapping: a dictionary from each digit to its corresponding letters.
  2. Use a recursive function that takes the current digit index and a current combination being built.
  3. Base case: when the index equals the length of the phone number, add the current combination to the result.
  4. Recursive step: for each letter mapped to the current digit, append it to the combination and recurse on the next digit.
  5. Return all collected combinations.

Pseudocode

KEYPAD = {
    "0": ["0"], "1": ["1"],
    "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"]
}

function phoneNumberMnemonics(phoneNumber):
    result = []
    current = array of size len(phoneNumber)
    generateCombinations(0, phoneNumber, current, result)
    return result

function generateCombinations(idx, phoneNumber, current, result):
    if idx == len(phoneNumber):
        result.append(join(current))
        return
    digit = phoneNumber[idx]
    for letter in KEYPAD[digit]:
        current[idx] = letter
        generateCombinations(idx + 1, phoneNumber, current, result)

Time & Space Complexity

  • Time: O(4^n * n) where n is the length of the phone number. In the worst case, every digit maps to 4 letters, giving 4^n combinations, and each combination takes O(n) to construct.
  • Space: O(4^n * n) for storing all combinations. The recursion stack uses O(n) space.

Key Insights

  • Using a mutable array for the current combination and only joining at the base case is more efficient than string concatenation at each level.
  • Digits 0 and 1 map to themselves, so they contribute a branching factor of 1 (no increase in combinations).
  • Digits 7 and 9 have 4 letters while others have 3, making the worst case 4^n rather than 3^n.
  • This is a Cartesian product problem: we compute the product of the letter sets for each digit.

Edge Cases

  • Empty phone number: return an empty list (or a list containing an empty string, depending on spec).
  • Phone number with only 0s and 1s: only one combination (the digits themselves).
  • Single digit: return the list of letters for that digit.
  • Very long phone numbers: output size grows exponentially, so practical limits apply.

Linked mentions