LeetCode 17: Letter Combinations of a Phone Number

Problem Statement

Given a string digits containing numbers from 2 to 9, return all possible letter combinations that the number could represent based on a telephone keypad mapping (e.g., 2 maps to "abc"). The string can be empty, and each digit maps to 3 or 4 letters.

Constraints

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

Example

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Explanation: 2 maps to "abc", 3 to "def", combining each pair.

Input: digits = ""
Output: []
Explanation: Empty string returns empty list.

Input: digits = "2"
Output: ["a","b","c"]
Explanation: 2 maps to "abc".

Understanding the Problem

We need to generate all possible letter combinations for a phone number like "23". For "23", 2 gives "abc" and 3 gives "def", so we combine them to get "ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf". It’s a combinatorial problem, and we’ll use a backtracking approach to build these combinations step by step.

Solution: Backtracking

Explanation

Use a recursive backtracking method to explore all combinations. Start with an empty string and add one digit’s letters at a time, building up until the full length matches the input.

  1. Handle Edge Case.
  • If digits is empty, return an empty list.
  1. Define Keypad Mapping.
  • Map each digit (2-9) to its letters (e.g., '2': "abc").
  1. Backtrack Recursively.
  • For each digit, take its letters and append them to current combinations, moving to the next digit.
  1. Return Result.
  • Collect all combinations when length matches input.

Step-by-Step Example

Example 1: digits = "23"

We have "23" and want all combinations.

  • Goal: Generate letter combinations for "23".
  • Result for reference: ["ad","ae","af","bd","be","bf","cd","ce","cf"].
  • Start: Map—2:"abc", 3:"def". Result list empty.
  • Step 1: Check empty.
    • "23" not empty, proceed.
  • Step 2: Start with "" (length 0).
    • Digit "2" (index 0), letters "abc".
    • Combine "" with "a" → "a".
    • Combine "" with "b" → "b".
    • Combine "" with "c" → "c".
    • Current: ["a", "b", "c"].
  • Step 3: Next digit "3" (index 1), letters "def".
    • From "a":
      • "a" + "d" → "ad".
      • "a" + "e" → "ae".
      • "a" + "f" → "af".
    • From "b":
      • "b" + "d" → "bd".
      • "b" + "e" → "be".
      • "b" + "f" → "bf".
    • From "c":
      • "c" + "d" → "cd".
      • "c" + "e" → "ce".
      • "c" + "f" → "cf".
    • Current: ["ad","ae","af","bd","be","bf","cd","ce","cf"].
  • Step 4: Length 2 matches input, stop.
  • Finish: Return ["ad","ae","af","bd","be","bf","cd","ce","cf"].

Example 2: digits = ""

Now, empty string "".

  • Goal: Find combinations.
  • Result for reference: [].
  • Start: Result empty.
  • Step 1: Check empty.
    • "" is empty, stop.
  • Finish: Return [].

Code

Here’s the Python code for LeetCode 17. It’s clear and works in Python 3.6+. Test it on Replit!

def letterCombinations(digits: str) -> list[str]:
    if not digits:
        return []

    # Keypad mapping
    digit_to_letters = {
        '2': "abc", '3': "def", '4': "ghi", '5': "jkl",
        '6': "mno", '7': "pqrs", '8': "tuv", '9': "wxyz"
    }

    result = [""]

    # Build combinations digit by digit
    for digit in digits:
        new_result = []
        for prefix in result:
            for letter in digit_to_letters[digit]:
                new_result.append(prefix + letter)
        result = new_result

    return result

Complexity

  • Time Complexity: O(4^N * N) – N is digits length, up to 4 letters per digit, N for string concatenation.
  • Space Complexity: O(4^N) – Stores all combinations in result list.

Efficiency Notes

This backtracking solution is efficient for the small constraint (N ≤ 4), producing all combinations systematically.

Key Insights

Tips to master LeetCode 17:

  • Build Stepwise: Start small and grow combinations—don’t try all at once.
  • Map Matters: Knowing 2-9 mappings is key—keep it handy!
  • Empty Check: Handle "" early to avoid unnecessary work.

Alternative: Recursive Backtracking

Explanation

Use recursion to build combinations by adding one letter at a time, backtracking when done. It’s similar but uses function calls instead of loops.

Code (Recursive Backtracking)

Here’s the recursive version, also efficient and clear.

def letterCombinationsRecursive(digits: str) -> list[str]:
    if not digits:
        return []

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

    def backtrack(index: int, current: str) -> None:
        if len(current) == len(digits):
            result.append(current)
            return

        for letter in digit_to_letters[digits[index]]:
            backtrack(index + 1, current + letter)

    result = []
    backtrack(0, "")
    return result

Complexity (Alternative)

  • Time Complexity: O(4^N * N) – Same as iterative, due to combinations and string building.
  • Space Complexity: O(4^N) – Result list, plus recursion stack O(N).

Additional Example

For digits = "34":

  • Goal: Combinations.
  • Reference: ["dg","dh","di","eg","eh","ei","fg","fh","fi"].
  • Steps: 3:"def", 4:"ghi", combine to 9 results.
  • Result: ["dg","dh","di","eg","eh","ei","fg","fh","fi"].

Edge Cases

  • Empty: "" – Returns [].
  • Single Digit: "7" – Returns ["p","q","r","s"].
  • Max Length: "2345" – Returns 81 combinations.

Final Thoughts

Both backtracking methods solve LeetCode 17 efficiently in Python. They’re great for interviews and combinatorial skills. Check LeetCode 15: 3Sum for more array fun! How would you adapt this for uppercase letters?