The O(n) Club: Letter Combinations of a Phone Number — Texting Like It’s 2001

The O(n) Club: Letter Combinations of a Phone Number — Texting Like It’s 2001

⚡ TL;DR

Your job: take a string of digits (2-9). Pretend you’re a bored teenager in 2001 hammering away at a Nokia to T9 your masterpiece. Generate every text combo you could make. You could brute-force it (nested loops until you turn into a fossil), or just backtrack like a real developer. Java snippet for the ancient brute-force way:

// Brute force for 3 digits (don't try this at home)
for (char c1 : map[digits.charAt(0)])
  for (char c2 : map[digits.charAt(1)])
    for (char c3 : map[digits.charAt(2)])
      results.add("" + c1 + c2 + c3);
// Add 20 more loops for a messier problem!

🧠 How Devs Usually Mess This Up

Ah, the rookie gauntlet:

🔍 What’s Actually Going On

This is a classic combinatorics tree problem disguised as a keypad riddle. Each phone digit spawns a level of choices—imagine climbing a tree where every branch is another possible character (‘2’ gets you ‘a’, ‘b’, or ‘c’; ‘3’ is ‘d’, ‘e’, ‘f’, etc.). You walk down the tree, stacking letters, and yell “Bingo!” every time you hit the last digit. It’s classic backtracking: try a letter, go deeper, undo and try again. Basically like repeatedly opening your fridge hoping cheese will appear.

🛠️ PseudoCode

• Map each digit (2-9) to its letter group.
  

  String[] map = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

• Create an output list to hold all combos.
  

  List<String> output = new ArrayList<>();

• Return empty list if the input is empty. No digits, no party.
• Write a recursive function:
  • If at the end: pop current string into output.
  • Otherwise: for each valid letter for this digit, append & recurse, then backtrack (aka clean up after your own mess).

  void backtrack(String digits, int idx, StringBuilder path) {
    if (idx == digits.length()) {
      output.add(path.toString());
      return;
    }
    for (char c : map[digits.charAt(idx) - '2'].toCharArray()) {
      path.append(c);
      backtrack(digits, idx+1, path);
      path.deleteCharAt(path.length()-1); // remove last
    }
  }

Think of it as: “Try a topping, go deeper, try another topping, backtrack. Rinse, repeat, eat pizza.”

💻 The Code

public List<String> letterCombinations(String digits) {
  String[] map = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
  List<String> output = new ArrayList<>();
  if (digits == null || digits.length() == 0) return output;
  backtrack(digits, 0, new StringBuilder(), map, output);
  return output;
}
private void backtrack(String digits, int idx, StringBuilder path, String[] map, List<String> output) {
  if (idx == digits.length()) {
    output.add(path.toString());
    return;
  }
  String letters = map[digits.charAt(idx) - '2'];
  for (char c : letters.toCharArray()) {
    path.append(c);
    backtrack(digits, idx+1, path, map, output);
    path.deleteCharAt(path.length()-1);
  }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Digits ‘0’ and ‘1’: Just ignore — they’re wallflowers at this Java party.
• Empty input: Return [], not [“”]. LeetCode judges have no chill about this.
• Exponential explosion! Output size is up to 4ⁿ. For 8 digits, maybe block out a weekend to review your result!
• Space: The list holds all combos. Recursion stack only as deep as the number of digits. (If you’re getting OOM, maybe your phone number is too ambitious.)

🧠 Interviewer Brain-Tattoo

“Brute force is a love letter to inefficiency. T9 texting taught us recursion—yes, your phone was smarter than you thought.”