We map each digit to its corresponding letters and use backtracking to generate all combinations by picking one letter from each digit's mapping.
- Create a digit-to-letters mapping.
- Start with an empty string and index 0.
- For each digit, iterate through its letters.
- Append a letter and recurse to the next digit.
- When the combination length equals the digits length, save it.
- Time Complexity: O(4^N) where N is the number of digits.
- Space Complexity: O(N) for the recursion stack.
def letter_combinations(digits):
if not digits:
return []
phone_map = {
'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
'6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
}
result = []
def backtrack(index, current):
if index == len(digits):
result.append(current)
return
for letter in phone_map[digits[index]]:
backtrack(index + 1, current + letter)
backtrack(0, '')
return result