Letter Combinations of a Phone Number
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.
A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Example 1:
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Example 2:
Input: digits = ""
Output: []
Example 3:
Input: digits = "2"
Output: ["a","b","c"]
Constraints:
0 <= digits.length <= 4digits[i]is a digit in the range['2', '9'].
Solve it on LeetCode
Approaches
1. Backtracking Approach
Intuition:
To solve the problem of generating all possible letter combinations given a string of digits mapped to letters as on a telephone keypad, we can use backtracking. This approach explores all possible solutions by building each combination step by step and then concatenating letters that map to each digit.
Each digit can map to a set of letters ("2" maps to "abc", "3" maps to "def", etc.), and the problem is to generate all permutations of these letters, constrained by the order of digits in the input.
When using backtracking:
- We recursively build each combination with the current letter, append it to our temporary string, and when the temporary string is the same length as the input digits, we have a full valid combination.
- Then we backtrack to substitute the last added letter with the others mapped by the same digit.
This method is efficient as it avoids constructing unnecessary paths once a valid one is found.
Code:
- Time Complexity: O(3^n × 4^m), where n is the number of digits mapping to 3 letters (like '2', '3', '4', etc.) and m is the number of digits mapping to 4 letters (like '7' or '9'). This complexity arises because we generate all possible combinations.
- Space Complexity: O(3^n × 4^m), since the space required is mainly due to the storage of results in the list.