The “Letter Combinations of a Phone Number“ problem is a classic question often asked in technical interviews. It challenges your understanding of backtracking, recursion, and efficient problem-solving. Let’s explore all possible solutions, from a naive approach to an optimized one, with their explanations, complexities, and Java implementations.
Problem Statement for Letter Combinations of a Phone Number
Given a string containing digits from 2 to 9, return all possible letter combinations that the number could represent. Each digit maps to a set of letters (like on a phone keypad). Return the combinations in any order.
A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
Example
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Input: digits = ""
Output: []
Key Insights
- Each digit maps to a group of letters, e.g.,
2 -> "abc",3 -> "def", etc. - The task is to generate all combinations of letters where each combination has one letter from each digit’s mapping.
Approach 1: Naive Solution Using Iterative Combination Building for Letter Combinations of a Phone Number
Explanation
This solution builds combinations iteratively by appending one letter at a time for each digit’s mapping. Although simple, it lacks elegance and efficiency for larger inputs.
Code
import java.util.*;
public class LetterCombinationsNaive {
public static List<String> letterCombinations(String digits) {
if (digits == null || digits.isEmpty()) return new ArrayList<>();
String[] mapping = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
List<String> combinations = new ArrayList<>();
combinations.add(""); // Start with an empty combination
for (char digit : digits.toCharArray()) {
List<String> temp = new ArrayList<>();
for (String combination : combinations) {
for (char letter : mapping[digit - '0'].toCharArray()) {
temp.add(combination + letter);
}
}
combinations = temp;
}
return combinations;
}
public static void main(String[] args) {
System.out.println(letterCombinations("23"));
}
}Complexity
- Time Complexity: O(3n⋅4m), where nnn is the number of digits mapping to 3 letters, and mmm is the number of digits mapping to 4 letters.
- Space Complexity: O(n⋅k) where k is the total number of combinations.
Approach 2: Recursive Backtracking solution for Letter Combinations of a Phone Number
Explanation
Backtracking is the most elegant solution. We recursively explore all paths, appending a letter for each digit at every step. If we exhaust all digits, we store the combination.
Code
import java.util.*;
public class LetterCombinationsRecursive {
public static List<String> letterCombinations(String digits) {
if (digits == null || digits.isEmpty()) return new ArrayList<>();
String[] mapping = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
List<String> result = new ArrayList<>();
backtrack(result, digits, mapping, new StringBuilder(), 0);
return result;
}
private static void backtrack(List<String> result, String digits, String[] mapping, StringBuilder current, int index) {
if (index == digits.length()) {
result.add(current.toString());
return;
}
String letters = mapping[digits.charAt(index) - '0'];
for (char letter : letters.toCharArray()) {
current.append(letter);
backtrack(result, digits, mapping, current, index + 1);
current.deleteCharAt(current.length() - 1); // Backtrack
}
}
public static void main(String[] args) {
System.out.println(letterCombinations("23"));
}
}Complexity
- Time Complexity: O(3n⋅4m).
- Space Complexity: O(n)(recursion stack depth).
Approach 3: Optimized Backtracking (Reducing Redundant Operations) for Letter Combinations of a Phone Number
Explanation
This approach is similar to the recursive one but optimizes letter traversal by reducing redundant operations or extra memory usage.
Code
import java.util.*;
public class LetterCombinationsOptimized {
public static List<String> letterCombinations(String digits) {
if (digits == null || digits.isEmpty()) return Collections.emptyList();
String[] mapping = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
List<String> result = new ArrayList<>();
backtrack(result, mapping, digits, 0, "");
return result;
}
private static void backtrack(List<String> result, String[] mapping, String digits, int index, String path) {
if (index == digits.length()) {
result.add(path);
return;
}
String letters = mapping[digits.charAt(index) - '0'];
for (char letter : letters.toCharArray()) {
backtrack(result, mapping, digits, index + 1, path + letter);
}
}
public static void main(String[] args) {
System.out.println(letterCombinations("23"));
}
}Complexity
- Time Complexity: O(3n⋅4m).
- Space Complexity: O(n).
Final Thoughts for Letter Combinations of a Phone Number
Each approach solves the problem but varies in readability, efficiency, and scalability:
| Approach | Complexity | Suitability |
|---|---|---|
| Iterative Combination | High | Simple but not recommended for large inputs. |
| Recursive Backtracking | Moderate | Best for clarity and moderate input sizes. |
| Optimized Backtracking | Moderate | More memory-efficient for practical applications. |
The backtracking approach is widely preferred for its clarity and efficiency. Depending on the constraints, you can use the naive or optimized version.