Definition
- Phone keypad mapping – digit 2 maps to "abc", 3 to "def", ..., 7 to "pqrs", 8 to "tuv", 9 to "wxyz".
- Backtracking – at each digit position, try every letter that digit maps to, append it, recurse to the next position, and remove it.
- Base case – when the index equals the digit string length, the current path is a complete combination.
- Result size – the product of letter counts per digit. Worst case (all 7s and 9s): 4^n combinations.
- Empty guard – if the input is empty, return an empty list immediately.
The National Bank of India lets customers create a vanity reference code by typing digits on a phone keypad, where each digit maps to several letters. For each digit, Priya tries each possible letter and moves to the next digit, building all possible spellings. Each complete spelling is one candidate code.
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 number could represent based on the classic phone keypad. This is LeetCode 17.
For example, "23" can spell: ad, ae, af, bd, be, bf, cd, ce, cf.
package com.bank.service;
// Phone keypad:
// 2 -> abc, 3 -> def, 4 -> ghi
// 5 -> jkl, 6 -> mno, 7 -> pqrs
// 8 -> tuv, 9 -> wxyz
// Input: "23"
// Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
How does the backtracking solution work?
Store the digit-to-letters mapping. Backtrack with an index into the digit string and a StringBuilder path. When the index equals the string length, record the path. Otherwise, loop over the current digit's letters, append one, recurse with index + 1, and remove it.
package com.bank.service;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
public class LetterCombinations {
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 List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<>();
if (digits == null || digits.isEmpty()) {
return result; // empty input -> empty list
}
backtrack(digits, 0, new StringBuilder(), result);
return result;
}
private void backtrack(String digits, int index,
StringBuilder path, List<String> result) {
if (index == digits.length()) {
result.add(path.toString()); // complete combination
return;
}
String letters = KEYPAD.get(digits.charAt(index));
for (char c : letters.toCharArray()) {
path.append(c);
backtrack(digits, index + 1, path, result);
path.deleteCharAt(path.length() - 1); // backtrack
}
}
public static void main(String[] args) {
LetterCombinations solver = new LetterCombinations();
System.out.println(solver.letterCombinations("23"));
}
}
[ad, ae, af, bd, be, bf, cd, ce, cf]
Why guard against empty input?
An empty digit string should return an empty list, not a list containing an empty string. Without the guard, the base case would fire immediately and record an empty string. This is a common edge case that trips candidates.
package com.bank.service;
public class EmptyGuardDemo {
public static void main(String[] args) {
LetterCombinations solver = new LetterCombinations();
System.out.println("Empty: " + solver.letterCombinations(""));
System.out.println("Null: " + solver.letterCombinations(null));
}
}
Empty: []
Null: []
How does the recursion tree look?
For "23", the tree has two levels. The first level branches on the letters of digit 2 (a, b, c). Each branch then branches on the letters of digit 3 (d, e, f). Every leaf is a complete combination.
(root)
/ | \
a b c ← digit '2' letters
/ | \ / | \ / | \
d e f d e f d e f ← digit '3' letters
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
ad ae af bd be bf cd ce cf
What about the iterative approach?
An iterative queue-based expansion produces the same result without recursion. Start with an empty string in a queue. For each digit, expand every partial combination by appending each letter, creating new partials. When all digits are consumed, the queue holds the complete combinations.
package com.bank.service;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
public class LetterCombinationsIterative {
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 List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<>();
if (digits == null || digits.isEmpty()) return result;
Queue<String> queue = new LinkedList<>();
queue.offer("");
for (char digit : digits.toCharArray()) {
String letters = KEYPAD.get(digit);
int size = queue.size();
for (int i = 0; i < size; i++) {
String partial = queue.poll();
for (char c : letters.toCharArray()) {
queue.offer(partial + c);
}
}
}
result.addAll(queue);
return result;
}
public static void main(String[] args) {
LetterCombinationsIterative solver = new LetterCombinationsIterative();
System.out.println(solver.letterCombinations("23"));
}
}
[ad, ae, af, bd, be, bf, cd, ce, cf]
How is this different from subsets or permutations?
This is a product-space enumeration, not a subset or permutation. At each position, the choices come from a different set (the letters of that digit), and every position must be filled. The result count is the product of the per-digit letter counts.
| Problem | Decision at each step | Result size |
|---|---|---|
| Subsets | Include or exclude each element | 2^n |
| Permutations | Choose from remaining elements | n! |
| Letter Combinations | Choose from that position's letter set | product of set sizes |
What about the banking domain use case?
At the National Bank of India, customers choose a memorable vanity code for a payee by typing keypad digits, and the system suggests every letter combination those digits could spell. The backtracking generates all suggestions, which are then filtered against a dictionary of valid words.
package com.bank.service;
import java.util.List;
public class VanityCodeGenerator {
public static void main(String[] args) {
LetterCombinations solver = new LetterCombinations();
String digits = "225"; // typed by customer
List<String> codes = solver.letterCombinations(digits);
System.out.println("Possible vanity codes for " + digits + ":");
System.out.println(codes.subList(0, Math.min(10, codes.size())));
System.out.println("Total: " + codes.size());
}
}
Possible vanity codes for 225:
[aaj, aak, aal, abj, abk, abl, acj, ack, acl, baj]
Total: 27
What are common interview follow-up questions?
- What is the time complexity? (O(4^n * n) worst case, because digits 7 and 9 have 4 letters.)
- What if the input contains 0 or 1? (These digits have no letter mapping; skip them or return empty.)
- Can you do it iteratively? (Yes, queue-based expansion.)
- What if you only want combinations that form valid words? (Add a dictionary lookup filter at the leaf.)
- What is the space complexity? (O(n) for the recursion depth plus O(result count * n) for the output.)
Visual Overview
Letter Combinations: digits = "23"
Phone keypad:
┌─────┬─────┬─────┐
│ 2 │ 3 │ 4 │
│ abc │ def │ ghi │
├─────┼─────┼─────┤
│ 5 │ 6 │ 7 │
│ jkl │ mno │pqrs │
├─────┼─────┼─────┤
│ 8 │ 9 │ │
│ tuv │wxyz │ │
└─────┴─────┴─────┘
Recursion tree for "23":
[]
/ | \
a b c
/|\ /|\ /|\
d e f d e f d e f
↓ ↓ ↓
ad... bd... cd...
Result: 3 * 3 = 9 combinations
Key Takeaway
Letter Combinations of a Phone Number is a product-space backtracking problem where each digit position independently contributes its own set of letters. You keep a digit-to-letters map, then recurse with an index into the digit string and a string builder. At each position you try every letter of the current digit, append it, recurse to the next digit, and remove it to backtrack. When the index reaches the end, you record the completed combination.
The important edge case is empty input, which must return an empty list, not a list containing an empty string. The worst-case cost is about 4^n * n because digits 7 and 9 have four letters each.
An iterative queue-based expansion gives the same result without recursion, which is useful when the digit count grows and stack depth becomes a concern. Both approaches produce combinations in the same order.
At the National Bank of India, this pattern powers the vanity code generator that suggests all letter combinations a customer's keypad digits could spell, filtering them against a dictionary to offer memorable payee references.
Remember one sentence: map each digit to its letters, backtrack across positions, and the result count is the product of per-digit letter counts.
---