Letter Combinations of a Phone Number
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. 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"
Examples
Constraints
0 <= digits.length <= 4`digits[i]` is a digit in the range `['2', '9']`.
Backtracking
Approach
We can find all possible combinations by simulating the button presses. 1. First, create a hash map or array that maps each digit to its corresponding string of letters. 2. Handle the edge case: if the `digits` string is empty, immediately return an empty list. 3. Define a recursive backtracking function that takes the current index in the `digits` string and the current string combination being built. 4. Base case: If the current index equals the length of `digits`, it means we have selected a letter for every digit. Add the current string combination to the results list. 5. Otherwise, find the letters corresponding to the current digit. 6. Loop through each letter. For each letter, append it to the current combination and recursively call the function for the next index (`index + 1`). 7. Since strings are immutable in Java/Python/JS (or we pass new strings), appending to the string and passing it directly in the recursive call intrinsically handles backtracking (the original string at the current call stack level remains unchanged).
Complexity Analysis
Where `n` is the length of digits. In the worst case (digits 7 or 9), each digit maps to 4 letters, leading to 4^n combinations. Copying each combination of length `n` takes O(n) time. The space complexity is O(n) for the recursion stack.