Definition
Letter Combinations of a Phone Number enumerates the Cartesian product of letter groups.
- Keypad mapping maps each digit (2-9) to its corresponding group of 3 or 4 letters.
- Backtracking fixes one letter for the current digit, recurses to the next digit, then removes to try the next letter.
- Base case is reached when the index equals the digit string length, and the current combination is recorded.
- Output size equals the product of the group sizes, and the work is proportional to that output size.
- Recursion depth equals the number of digits, so the search is always shallow.
At National Bank of India, customers sometimes remember a vanity branch phone code by its letters, and support needs every letter spelling a digit code could map to so they can match it against known branch words. Each digit offers a small group of letters. They pick one letter for the first digit, then one for the next, building up every full spelling.
Understanding the Concepts
What is the Letter Combinations Problem?
Given a string of digits from 2 to 9, return all possible letter combinations that the digits could represent on a classic phone keypad. Digit 2 maps to "abc", digit 3 to "def", and so on. This is a Cartesian product of the letter groups.
At National Bank of India, the support team needs to decode vanity phone codes by generating all possible letter spellings.
package com.bank.service;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
public class PhoneLetterCombinations {
private static final Map<Character, String> KEYPAD = Map.of(
'2', "abc", '3', "def", '4', "ghi", '5', "jkl",
'6', "mno", '7', "pqrs", '8', "tuv", '9', "wxyz"
);
public static List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<>();
if (digits == null || digits.isEmpty()) return result;
backtrack(digits, 0, new StringBuilder(), result);
return result;
}
private static void backtrack(String digits, int index,
StringBuilder current, List<String> result) {
if (index == digits.length()) {
result.add(current.toString());
return;
}
String letters = KEYPAD.get(digits.charAt(index));
for (char letter : letters.toCharArray()) {
current.append(letter);
backtrack(digits, index + 1, current, result);
current.deleteCharAt(current.length() - 1); // backtrack
}
}
public static void main(String[] args) {
List<String> combos = letterCombinations("23");
System.out.println("Combinations for 23: " + combos);
System.out.println("Count: " + combos.size());
}
}
Combinations for 23: [ad, ae, af, bd, be, bf, cd, ce, cf]
Count: 9
Why Does This Problem Matter?
This problem teaches the Cartesian product pattern in backtracking. Each digit position is independent: the choice at one position does not restrict choices at another. This makes it a clean introduction to multi-dimensional enumeration.
In banking, the pattern applies when Rajesh needs to generate all possible codes from a set of independent digit groups, such as validating partial account reference codes.
package com.bank.service;
public class CartesianProductExample {
// The total output is the product of group sizes
public static int totalCombinations(String digits) {
int total = 1;
Map<Character, String> keypad = Map.of(
'2', "abc", '3', "def", '4', "ghi", '5', "jkl",
'6', "mno", '7', "pqrs", '8', "tuv", '9', "wxyz");
for (char d : digits.toCharArray()) {
total *= keypad.get(d).length();
}
return total;
}
}
How Does the Backtracking Work Internally?
The recursion has a clear structure: we carry an index into the digit string and a StringBuilder for the current combination. At each level we look up the letters for the current digit and loop over them. For each letter we append it, recurse to the next index, then remove it.
The recursion depth equals the number of digits, which is at most 4 for a phone number segment, so the search is very shallow.
package com.bank.core;
import java.util.Map;
public class BacktrackingTrace {
private static final Map<Character, String> KEYPAD = Map.of(
'2', "abc", '3', "def");
public static void trace(String digits, int index, StringBuilder current, int depth) {
String indent = " ".repeat(depth);
if (index == digits.length()) {
System.out.println(indent + "RECORD: " + current);
return;
}
String letters = KEYPAD.get(digits.charAt(index));
for (char letter : letters.toCharArray()) {
System.out.println(indent + "TRY: " + letter);
current.append(letter);
trace(digits, index + 1, current, depth + 1);
current.deleteCharAt(current.length() - 1);
}
}
public static void main(String[] args) {
trace("23", 0, new StringBuilder(), 0);
}
}
TRY: a
TRY: d
RECORD: ad
TRY: e
RECORD: ae
TRY: f
RECORD: af
TRY: b
TRY: d
RECORD: bd
TRY: e
RECORD: be
TRY: f
RECORD: bf
TRY: c
TRY: d
RECORD: cd
TRY: e
RECORD: ce
TRY: f
RECORD: cf
How Is This Different from Permutations?
| Aspect | Letter Combinations | Permutations |
|---|---|---|
| Source of choices | Each digit has its own fixed letter set | All elements share one pool |
| Reuse | No reuse needed, each digit is independent | Each element used exactly once |
| Output size | Product of group sizes | n! |
| Tracking used | Not needed | Boolean used array |
| Recursion depth | Number of digits | Number of elements |
// Letter combinations: 3 letters for digit 2, 3 for digit 3 -> 3*3 = 9
// Permutations of 3 elements: 3! = 6
What Are the Edge Cases?
The main edge case is an empty input string. The convention is to return an empty list, not a list containing one empty string. Another edge case is a single digit, which returns the individual letters of that digit's group.
package com.bank.core;
import java.util.List;
public class PhoneEdgeCases {
public static void main(String[] args) {
// Empty input returns empty list
List<String> empty = PhoneLetterCombinations.letterCombinations("");
System.out.println("Empty input: " + empty); // []
// Single digit
List<String> single = PhoneLetterCombinations.letterCombinations("7");
System.out.println("Single digit 7: " + single); // [p, q, r, s]
// Digits 7 and 9 have 4 letters
List<String> fourLetters = PhoneLetterCombinations.letterCombinations("79");
System.out.println("79 count: " + fourLetters.size()); // 4*4 = 16
}
}
Empty input: []
Single digit 7: [p, q, r, s]
79 count: 16
What Are the Limitations?
The output grows as the product of group sizes. For a 7-digit phone number where each digit maps to 3 letters, there are 3^7 = 2187 combinations. For digits 7 and 9 with 4 letters, the branching is higher. However, phone numbers are short, so the total output stays manageable.
package com.bank.core;
public class PhoneFeasibility {
public static void main(String[] args) {
// Worst case: all digits are 7 or 9 (4 letters each)
for (int digits = 1; digits <= 10; digits++) {
long count = (long) Math.pow(4, digits);
System.out.println(digits + " digits (worst) -> " + count + " combos");
}
}
}
1 digits (worst) -> 4 combos
2 digits (worst) -> 16 combos
3 digits (worst) -> 64 combos
4 digits (worst) -> 256 combos
5 digits (worst) -> 1024 combos
6 digits (worst) -> 4096 combos
7 digits (worst) -> 16384 combos
8 digits (worst) -> 65536 combos
9 digits (worst) -> 262144 combos
10 digits (worst) -> 1048576 combos
What About an Iterative BFS Approach?
Instead of backtracking, you can use a queue-based breadth-first approach. Start with an empty string in the queue, and for each digit dequeue all current entries and enqueue new entries with each possible letter appended.
package com.bank.core;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
public class PhoneLetterBFS {
public static List<String> letterCombinations(String digits) {
if (digits.isEmpty()) return new ArrayList<>();
Map<Character, String> keypad = Map.of(
'2', "abc", '3', "def", '4', "ghi", '5', "jkl",
'6', "mno", '7', "pqrs", '8', "tuv", '9', "wxyz");
Queue<String> queue = new LinkedList<>();
queue.add("");
for (char digit : digits.toCharArray()) {
int size = queue.size();
String letters = keypad.get(digit);
for (int i = 0; i < size; i++) {
String prefix = queue.poll();
for (char letter : letters.toCharArray()) {
queue.add(prefix + letter);
}
}
}
return new ArrayList<>(queue);
}
}
What Are Common Interview Follow-Up Questions?
Interviewers commonly ask these follow-ups:
- Filter results against a dictionary to find real words. This turns it into a T9 predictive text problem.
- Count the combinations without generating them. The answer is the product of the group sizes.
- Handle the 0 and 1 keys which have no letters. Skip them during recursion.
- What if the digit string is very long? The output is exponential, so streaming results or early termination with a dictionary filter is needed.
package com.bank.core;
import java.util.Set;
public class T9Filter {
public static void findWords(String digits, Set<String> dictionary) {
List<String> all = PhoneLetterCombinations.letterCombinations(digits);
for (String combo : all) {
if (dictionary.contains(combo)) {
System.out.println("Match: " + combo);
}
}
}
}
Visual Overview
Phone Keypad Mapping:
┌─────┬─────┬─────┐
│ 1 │ 2 │ 3 │
│ │ abc │ def │
├─────┼─────┼─────┤
│ 4 │ 5 │ 6 │
│ ghi │ jkl │ mno │
├─────┼─────┼─────┤
│ 7 │ 8 │ 9 │
│pqrs │ tuv │wxyz │
└─────┴─────┴─────┘
Backtracking for digits "23":
digit 2 (abc)
┌────┼────┐
a b c
│ │ │
digit 3 (def)
┌─┼─┐ ┌─┼─┐ ┌─┼─┐
d e f d e f d e f
│ │ │ │ │ │ │ │ │
ad ae af bd be bf cd ce cf
Output: 3 * 3 = 9 combinations
Key Takeaway
Letter Combinations of a Phone Number enumerates every letter spelling that a string of keypad digits could represent, which is exactly the Cartesian product of the letter groups mapped to each digit. I solve it with backtracking: I keep a mapping from each digit to its letters, and I recurse over the digit positions. At each position I loop over the letters for that digit, appending one, recursing to the next position, and then removing it to try the next letter.
The point I make is that although the output can be large, the recursion depth is only the number of digits, so the search is shallow and the cost is proportional to the number of spellings it must produce. I also handle the conventional edge case where an empty input returns an empty list rather than a single empty string.
At National Bank of India I used this in support tooling for vanity branch phone codes, generating every letter spelling of a short digit code to match against a dictionary of branch words. I backtracked over the digit positions with an immutable keypad map and trimmed the builder after each branch.
The key distinctions are that digits 7 and 9 have four letters while the others have three, so the branching is non-uniform and the total count is the product of the group sizes. An iterative BFS approach is an alternative that avoids recursion entirely.
Remember one sentence: for each digit try every mapped letter, recurse to the next digit, and record the combination when all digits are assigned.
---