Letter Combinations of Phone Number
Mahabharata — The Cipher of Digits — All Words That Can Be Spelled from a Number
प्रत्येक अंक — अक्षरों का समूह। हर अक्षर जोड़ो — अगले अंक के हर अक्षर से॥
*Each digit — a group of letters. Add each letter — combine with every letter of the next digit.*
The Story
Given a string of digits 2-9, return all possible letter combinations (phone keypad mapping).
For `digits="23"`: ["ad","ae","af","bd","be","bf","cd","ce","cf"].
Phone mapping: 2→abc, 3→def, 4→ghi, 5→jkl, 6→mno, 7→pqrs, 8→tuv, 9→wxyz
**Backtracking:** - For each digit, try each letter it maps to - Append the letter to current combination, recurse for next digit, backtrack
```java String[] map = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; void backtrack(List<String> res, String digits, int idx, StringBuilder sb) { if (idx == digits.length()) { res.add(sb.toString()); return; } String letters = map[digits.charAt(idx) - '0']; for (char c : letters.toCharArray()) { sb.append(c); // Choose backtrack(res, digits, idx+1, sb); // Explore sb.deleteCharAt(sb.length()-1); // Unchoose (backtrack!) } } ```
Trace `"23"`: - idx=0 (digit '2'): letters="abc" - sb="a": idx=1 (digit '3'): letters="def" - sb="ad" → add, sb="ae" → add, sb="af" → add - sb="b": → "bd","be","bf" - sb="c": → "cd","ce","cf"
**This is explicit backtracking:** We use a StringBuilder and explicitly undo (deleteCharAt) after each recursive call. This is the classic Choose → Explore → Unchoose pattern.
The Iterative Product Approach
Build combinations iteratively: start with [""], for each digit expand each combination with each letter. O(4^n × n).
public List<String> letterCombinationsIterative(String digits) {
if (digits.isEmpty()) return new ArrayList<>();
String[] map={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
List<String> res=new ArrayList<>(Arrays.asList(""));
for (char d : digits.toCharArray()) {
List<String> next=new ArrayList<>();
for (String s : res) for (char c : map[d-'0'].toCharArray()) next.add(s+c);
res=next;
}
return res;
}The Choose-Explore-Unchoose Backtracking
public List<String> letterCombinations(String digits) {
if (digits.isEmpty()) return new ArrayList<>();
String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
List<String> res = new ArrayList<>();
backtrack(res, digits, 0, new StringBuilder(), map);
return res;
}
void backtrack(List<String> res, String digits, int idx, StringBuilder sb, String[] map) {
if (idx == digits.length()) { res.add(sb.toString()); return; }
for (char c : map[digits.charAt(idx) - '0'].toCharArray()) {
sb.append(c); // Choose
backtrack(res, digits, idx+1, sb, map); // Explore
sb.deleteCharAt(sb.length()-1); // Unchoose
}
}Step-by-Step Walkthrough
digits="" → return [] ✅ digits="9" → map[9]="wxyz" → ["w","x","y","z"] ✅
Deep Insight
**The Choose-Explore-Unchoose template:** This is the canonical backtracking pattern: ``` for each choice: make the choice recurse undo the choice ``` Every backtracking problem (Permutations, N-Queens, Sudoku, etc.) follows this template.
**StringBuilder vs String concatenation:** StringBuilder with deleteCharAt is O(1) per choice/unchoice. String concatenation creates new strings each time (O(n)). Always use StringBuilder for backtracking.
**Why it's O(4^n × n)?** Each digit maps to at most 4 letters (7→pqrs, 9→wxyz). With n digits: at most 4^n combinations, each of length n to copy into the result.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(4^n × n) | O(n) | Same complexity as backtracking |
| Optimal | O(4^n × n) | O(n) | 4^n combinations, n chars each to add to result |
Pattern Recognition
✅ Phone number → letter combinations ✅ Choose-Explore-Unchoose backtracking template ✅ StringBuilder + deleteCharAt for efficient undo ✅ idx tracks position in digits string **LeetCode Trigger Phrases:** → "letter combinations of a phone number" → Generate all strings from character groups → Multi-level backtracking
Bhagavad Gita 11.10
अनेकवक्त्रनयनमनेकाद्भुतदर्शनम्। अनेकदिव्याभरणं दिव्यानेकोद्यतायुधम्॥
With many faces and eyes, with many wonderful sights, with many divine ornaments, with many divine uplifted weapons.
Connection: The cosmic form reveals countless combinations — each aspect multiplying with others to create infinite manifestations. The phone number backtracking similarly generates all combinations: each digit's letters multiply with every choice from the next digit. Like Krishna's cosmic revelation where each form combines with every other to reveal infinite variety, the algorithm systematically generates every combination of letters, exploring each path to completion before returning to try the next.