Letter Combinations of a Phone Number

Given a digit string (2-9), return all possible letter combinations based on telephone keypad mapping. Order does not matter.

Function signature

func LetterCombinations(digits string) []string

Inputs / outputs

• digits: string of digits 2-9.
• Return: all possible letter combinations.

Example

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

Constraints

• 0 <= len(digits) <= 4

Core idea (near-solution)

This is a Cartesian product over digit-to-letter mappings. Use backtracking to build one character at a time.

Invariant: the current path has length i and matches the first i digits.

Algorithm (step-by-step)

1. If digits is empty, return empty slice.
2. Map digits to letter strings ("2" -> "abc", etc.).
3. DFS with index i and buffer path:
   • If i == len(digits), record the string.
   • For each letter in mapping[digits[i]], append and recurse.
4. Return the results.

Correctness sketch

• Invariant: the current path has length i and matches the first i digits.
• Each recursive step extends a valid partial solution.
• Backtracking explores all possible choices without duplication.
• Thus every valid solution is found and recorded.

Trace (hand walkthrough)

Example input:
digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Walk:
- digits "2" -> [a,b,c]
- extend with "3" (d,e,f) -> ad, ae, af, bd, be, bf, cd, ce, cf

Pitfalls to avoid

• Returning []string{""} for empty input (should be empty).
• Using rune-based iteration incorrectly (letters are ASCII here).

Complexity

• Time: O(3^n) to O(4^n) depending on digits.
• Extra space: O(n) recursion depth (excluding output).

Implementation notes (Go)

• Use a []byte buffer for the current path and convert to string on output.