Letter Combinations of a Phone Number
LeetCode #17 · Medium · Backtracking · C++ solution with worked-out approach and complexity analysis.
Approach
Iterative (BFS)
Start with an empty string in the result. For each digit, expand every existing string in the result by appending all possible letters corresponding to that digit.
Time
O(4^n * n)
n is the length of digits.
Space
O(4^n * n)
to store the result.
Problem description(from LeetCode)
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.
Examples
Example 1
- Input:
- digits = "23"
- Output:
- ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Constraints
- •0 <= digits.length <= 4
- •digits[i] is a digit in the range ['2', '9'].
C++ Solution
solution.cpp
class Solution {
public:
vector<string> letterCombinations(string digits) {
vector<string> mapping = {"", "", "abc", "def", "ghi",
"jkl", "mno", "pqrs", "tuv", "wxyz"};
vector<string> result = {""};
for (char digit : digits) {
string letters = mapping[digit - '0'];
vector<string> newCombinations;
for (const string &prefix : result) {
for (char letter : letters) {
newCombinations.push_back(prefix + letter);
}
}
result = newCombinations;
}
return result;
}
};