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 <iostream>
2#include <vector>
3
4class Solution {
5public:
6 std::vector<std::string> letterCombinations(std::string digits) {
7 if (digits.empty()) return {};
8 std::vector<std::string> phoneMap = {
9 "", "", "abc", "def",
10 "ghi", "jkl", "mno",
11 "pqrs", "tuv", "wxyz"
12 };
13 std::vector<std::string> combinations;
14 backtrack(combinations, phoneMap, digits, 0, "");
15 return combinations;
16 }
17
18private:
19 void backtrack(std::vector<std::string>& combinations,
20 const std::vector<std::string>& phoneMap,
21 const std::string& digits,
22 int index,
23 std::string current) {
24 if (index == digits.size()) {
25 combinations.push_back(current);
26 return;
27 }
28 std::string letters = phoneMap[digits[index] - '0'];
29 for (char letter : letters) {
30 backtrack(combinations, phoneMap, digits, index + 1, current + letter);
31 }
32 }
33};
34
35int main() {
36 Solution s;
37 std::vector<std::string> result = s.letterCombinations("23");
38 for (const std::string& str : result) {
39 std::cout << str << " ";
40 }
41 return 0;
42}In this C++ solution, we maintain the recursive principle and build up combinations by appending each potential letter from the phone keypad mapping to the current string. Once a combination is complete, it's saved to the results.
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.
The Python solution leverages a queue (deque) to perform BFS-style exploration of all letter combinations. Initially, it stores an empty string, and iteratively enqueues combinations by appending the letters mapped from current digits. The process continues until all digits have been covered, emerging with a full spectrum of possible sequences.