17. Letter Combinations of a Phone Number
1. 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.
2. Example
Example 1
Input: digits = “23”
Output: [“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]
Example 2
Input: digits = “2”
Output: [“a”,“b”,“c”]
3. Constraints
- 0 <= digits.length <= 4
- digits[i] is a digit in the range [‘2’, ‘9’].
4. Solutions
Backtracking
m is the number of digits that map to 3 letters, n is the number of digits that map to 4 letters
Time complexity: O($3^m4^n$)
Space complexity: O(m + n)
class Solution {
public:
vector<string> letterCombinations(const string &digits) {
static constexpr array<string_view, 8> letters = {
"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
string combination;
combination.reserve(digits.size());
vector<string> combinations;
find_combinations(digits, 0, letters, combination, combinations);
return combinations;
}
private:
void find_combinations(
const string &digits,
int index,
const array<string_view, 8> &letters,
string &combination,
vector<string> &combinations) {
if (index == digits.size()) {
combinations.push_back(combination);
} else {
for (char letter : letters[digits[index] - '2']) {
combination.push_back(letter);
find_combinations(digits, index + 1, letters, combination, combinations);
combination.pop_back();
}
}
}
};