Leetcode 17: Letter Combinations of a Phone Number

 

1. Problem Statement (Simple Explanation):

You’re given a string digits consisting of characters '2'–'9'.

Each digit maps to some letters like on a classic phone keypad:

• 2 → "abc"

• 3 → "def"

• 4 → "ghi"

• 5 → "jkl"

• 6 → "mno"

• 7 → "pqrs"

• 8 → "tuv"

• 9 → "wxyz"

You need to return all possible letter combinations that the input number could represent.

• Order of combinations does not matter.

• If digits is empty, the answer is an empty list (LeetCode variant usually states that; here constraints start from length 1).

2. Examples:

Example 1:

Input: digits = "23"

Digit-to-letters:

• 2 → ["a","b","c"]

• 3 → ["d","e","f"]

All combinations (cartesian product):

• "a" + "d" = "ad"

• "a" + "e" = "ae"

• "a" + "f" = "af"

• "b" + "d" = "bd"

• "b" + "e" = "be"

• "b" + "f" = "bf"

• "c" + "d" = "cd"

• "c" + "e" = "ce"

• "c" + "f" = "cf"

Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:

Input: digits = "2"

Output: ["a","b","c"]

Constraints:

• 1<=digits.length<=41

• digits[i] is in '2'–'9'

3. Approach – Backtracking / DFS (Standard):

This is a classic backtracking (depth-first search) problem.

Intuition:

We build combinations digit by digit:

• At position i in digits, we choose one letter from the mapping of digits[i], append it to the current path, and recurse to fill the next position.

• When our current combination length equals len(digits), we have a complete combination; add it to the result.

Since digits.length <= 4 and each digit maps to at most 4 letters (7/9 → 4 letters), the total combinations are at most:

44-256

Very small, so recursive backtracking is perfect.

Algorithm (Step-by-Step):

1. If digits is empty, return empty list.

2. Create a mapping from digit char to its string of letters:

• '2' → "abc", '3' → "def", ..., '9' → "wxyz".

3. Create an empty list result to store combinations.

4. Define a recursive function backtrack(index, currentCombination):

• If index == len(digits):

• We formed a full combination → add currentCombination to result, return.

• Else:

• Let digit = digits[index].

• Let letters = mapping[digit].

• For each letter in letters:

• Append letter to currentCombination.

• Call backtrack(index + 1, currentCombination).

• Remove letter (backtrack) if using a mutable builder.

5. Call backtrack(0, "").

6. Return result.

Pseudo-code:

Complexity:

Let:

• n = len(digits) (max 4)

• Each digit maps to up to 4 letters.

Number of combinations: at most 4n.

• Time: O(4n)

• Space:

• Recursion depth at most n.

• Result list stores all combinations. So asymptotic auxiliary space is O(n) (excluding output).

4. Java code:

5. C code:

6. C++ code:

7. Python code:

8. JavaScript code: