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.
1def letterCombinations(digits):
2 if not digits:
3 return []
4
5 phone_map = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
6 '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
7
8 def backtrack(index, path):
9 # If the current combination is complete
10 if len(path) == len(digits):
11 combinations.append(''.join(path))
12 return
13
14 # Get the letters that the current digit maps to, and loop through them
15 possible_letters = phone_map[digits[index]]
16 for letter in possible_letters:
17 # Add the letter to our current path and move to the next digit
18 path.append(letter)
19 backtrack(index + 1, path)
20 path.pop() # Backtrack by removing the letter
21
22 combinations = []
23 backtrack(0, [])
24 return combinations
25# Example use
26print(letterCombinations('23'))This Python solution utilizes a recursive helper method backtrack to explore all combinations by trying each possible letter for each digit sequentially. The base case is when the length of the path equals the number of digits, signifying a complete combination has been constructed. The combinations list accumulates all completed combinations, which is then returned as the result.
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.