Problem Description
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.
Key Insights
- Each digit maps to a set of letters similar to a telephone keypad.
- The problem can be solved using backtracking to explore all combinations of letters.
- An empty input should return an empty list.
- The maximum input length is 4, making it feasible to generate combinations using recursion.
Space and Time Complexity
Time Complexity: O(3^n * 4^m), where n is the number of digits that map to 3 letters and m is the number of digits that map to 4 letters. Space Complexity: O(n), where n is the depth of the recursive call stack.
Solution
To solve the problem, we can use a backtracking approach. We set up a mapping of each digit to its corresponding letters. We then recursively build combinations of letters by iterating over the digits and appending the possible letters to a temporary combination until we reach the length of the input digits. Once a complete combination is formed, we add it to the result list.