Sponsored
Sponsored
This approach uses recursion to explore all possible combinations represented by the digit-to-letter mapping of a phone keypad. We incrementally build letter combinations by allocating one letter per digit, and then explore further by making recursive calls.
The recursion depth is determined by the number of digits and the choices per digit. At each step, the algorithm branches into as many recursive calls as there are letters assigned to the current digit, continuing until all digits have been processed.
Time Complexity: O(3^n * 4^m), where n is the number of digits that map to 3 letters, and m is the number of digits that map to 4 letters.
Space Complexity: O(n), the maximum depth of the recursion stack is n.
1#include <stdio.h>
2#include <string.h>
3
4void backtrack(char ***result, int *returnSize, char *digits
The C solution follows the same recursive backtracking strategy, with the notable addition of manual memory management. The function allocates space to store combinations, modifies the path character array at each recursion level, and backtracks to explore all options.
The iterative BFS approach systematically explores all possible combinations of letter sequences by progressively building up combinations using a queue. It starts by enqueueing an empty string, and then, for each digit from the input, extends through all mapped letters, enqueuing partial solutions until all digits have been processed.
This method mimics the complete depth-first search but layers on combinations iteratively, capitalizing on the breadth search over immediate digit map expansion.
Time Complexity: O(3^n * 4^m), as methodically layers through the digit-letter expansion uniformly across a queue.
Space Complexity: O(n * 3^n * 4^m), where queue storage inflates in tandem with combination depth.
#include <vector>
#include <queue>
class Solution {
public:
std::vector<std::string> letterCombinations(std::string digits) {
std::vector<std::string> combinations;
if (digits.empty()) return combinations;
std::vector<std::string> phoneMap = {
"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
};
std::queue<std::string> q;
q.push("");
for (char digit : digits) {
int level_size = q.size();
for (int i = 0; i < level_size; i++) {
std::string prev_combination = q.front();
q.pop();
for (char letter : phoneMap[digit - '0']) {
q.push(prev_combination + letter);
}
}
}
while (!q.empty()) {
combinations.push_back(q.front());
q.pop();
}
return combinations;
}
int main() {
Solution s;
std::vector<std::string> result = s.letterCombinations("23");
for (const std::string& str : result) {
std::cout << str << " ";
}
return 0;
}
};Similarly, C++ employs a queue to facilitate straightforward, iterative letter exploration. Here, combinations are iteratively grown as each digit proposes expanded possibilities, generating a list after completely traversing the input.