Letter Combinations of a Phone Number

Medium

backtracking

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the digit could represent. Return the answer in any order.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

2 -> abc, 3 -> def, 4 -> ghi, 5 -> jkl, 6 -> mno, 7 -> pqrs, 8 -> tuv, 9 -> wxyz

This is a classic backtracking problem where at each digit position, we try all possible letters that digit maps to, then recurse to the next digit.

The total combinations = product of letters for each digit. For "23", that's 3 * 3 = 9 combinations.

Example 1

Input: digits = "23"

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

Explanation: 2 maps to "abc", 3 maps to "def". All 9 combinations of one letter from each.

Example 2

Input: digits = ""

Output: []

Explanation: Empty input produces no combinations.

Example 3

Input: digits = "2"

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

Explanation: Single digit 2 maps to three letters.

Constraints

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

Show Hints (4)

Hint 1: Create a mapping from each digit to its corresponding letters.

Hint 2: Process one digit at a time. For each digit, try each possible letter.

Hint 3: After trying a letter, move to the next digit. When all digits are processed, save the result.

Hint 4: This is similar to generating the Cartesian product of multiple sets.

Loading editor...

Test Results

Click "Run" to execute your code against test cases

AI Tutor

Socratic guidance - I'll ask questions, not give answers

AI Tutor

Hello! I'm your AI tutor, here to guide you through this problem using the Socratic method. I won't give you direct answers, but I'll ask questions and provide hints to help you discover the solution yourself. What's your first instinct when you look at this problem? What approach comes to mind?