Letter Combinations of a Phone Number

Given a string digits containing digits from 2 to 9, return every possible letter combination the number could represent.

Use the classic phone keypad mapping where 2 maps to "abc", 3 maps to "def", 4 maps to "ghi", 5 maps to "jkl", 6 maps to "mno", 7 maps to "pqrs", 8 maps to "tuv", and 9 maps to "wxyz".

Return the combinations in any order. If digits is empty, return an empty array.

Examples

Example 1:

Input: digits = "23"

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

Example 2:

Input: digits = ""

Output: []

Example 3:

Input: digits = "7"

Output: ["p","q","r","s"]

Constraints

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

Company Notes

Reported as a standard backtracking question with follow-up discussion around recursion structure and iterative generation tradeoffs.