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.

Handle Edge Case.

If digits is empty, return an empty list.

Define Keypad Mapping.

Map each digit (2-9) to its letters (e.g., '2': "abc").

Backtrack Recursively.

For each digit, take its letters and append them to current combinations, moving to the next digit.

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?