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.
1import java.util.ArrayList;
2import java.util.List;
3
4class Solution {
5 private final String[] phoneMap = {
6 "", "", "abc", "def",
7 "ghi", "jkl", "mno",
8 "pqrs", "tuv", "wxyz"
9 };
10
11 public List<String> letterCombinations(String digits) {
12 List<String> combinations = new ArrayList<>();
13 if (digits.length() == 0) {
14 return combinations;
15 }
16 backtrack(combinations, new StringBuilder(), digits, 0);
17 return combinations;
18 }
19
20 private void backtrack(List<String> combinations, StringBuilder path, String digits, int index) {
21 if (path.length() == digits.length()) {
22 combinations.add(path.toString());
23 return;
24 }
25
26 String possibleLetters = phoneMap[digits.charAt(index) - '0'];
27 for (char letter : possibleLetters.toCharArray()) {
28 path.append(letter);
29 backtrack(combinations, path, digits, index + 1);
30 path.deleteCharAt(path.length() - 1); // Backtrack
31 }
32 }
33
34 public static void main(String[] args) {
35 Solution sol = new Solution();
36 System.out.println(sol.letterCombinations("23"));
37 }
38}The Java solution implements the same recursive method using the backtrack to construct all letter combinations. The function backtrack appends each letter of the current digit to the StringBuilder, moving deeper in the recursion. Upon reaching a complete pass (all digits processed), it adds the combination to the results list.
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.