Letter Combinations of a Phone Number

This challenge asks you to generate all possible letter combinations that a phone number can map to. Phone numbers are represented as strings of digits, and each digit corresponds to a set of letters on a standard phone keypad. This problem is a classic example of backtracking and exploring combinations, useful for understanding recursive algorithms and generating permutations.

Problem Description

Given a string digits containing only digits from '2' to '9', return all possible letter combinations that the digits could represent. Each digit maps to a different set of letters on a phone keypad (see the mapping below). The output should be a list of strings, where each string represents a valid combination.

Phone Keypad Mapping:

2: "abc"
3: "def"
4: "ghi"
5: "jkl"
6: "mno"
7: "pqrs"
8: "tuv"
9: "wxyz"

What needs to be achieved:

Create a function that takes a string of digits as input.
Map each digit to its corresponding letters.
Generate all possible combinations of letters.
Return a list of strings, where each string is a valid combination.

Key Requirements:

The input string digits will only contain digits from '2' to '9'.
The output list should contain all possible combinations, without duplicates.
The order of the combinations in the output list does not matter.

Expected Behavior:

The function should return an empty list if the input string is empty. It should correctly generate combinations for single-digit and multi-digit inputs.

Edge Cases to Consider:

Empty input string.
Input string with only one digit.
Input string with multiple digits.
Handling invalid input characters (although the problem states only digits 2-9 are expected, consider how your solution would behave if it encountered other characters).

Examples

Example 1:

Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
Explanation: The digit '2' maps to "abc" and the digit '3' maps to "def".  Combining each letter from "abc" with each letter from "def" gives us the listed combinations.

Example 2:

Input: ""
Output: []
Explanation: An empty input string results in an empty output list.

Example 3:

Input: "2"
Output: ["a", "b", "c"]
Explanation: The digit '2' maps to "abc", so the output is a list containing each letter individually.

Constraints

The length of the input string digits can be between 0 and 9 inclusive.
The input string digits will only contain digits from '2' to '9'.
The number of possible combinations can be large (up to 4^9 = 262,144). Consider efficiency.

Notes

A recursive backtracking approach is well-suited for this problem. Think about how you can build up combinations incrementally, exploring each possible letter for each digit. A dictionary or hashmap can be useful for storing the digit-to-letter mapping. Consider how to avoid generating duplicate combinations. The order in which you explore the letters for each digit can affect the order of the combinations in the output.