264. Letter Combinations of a Phone Number

🔗 LeetCode Problem: 17. Letter Combinations of a Phone Number
📊 Difficulty: Medium
🏷️ Topics: Backtracking, Recursion

Problem Statement

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

A mapping of digits to letters (just like on telephone buttons):

2 → "abc"
3 → "def"
4 → "ghi"
5 → "jkl"
6 → "mno"
7 → "pqrs"
8 → "tuv"
9 → "wxyz"

Example 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:

Input: digits = ""
Output: []

Example 3:

Input: digits = "2"
Output: ["a","b","c"]

Constraints: - 0 <= digits.length <= 4 - digits[i] is a digit in the range ['2', '9'].

---

Understanding the Problem

Let me work through digits = "23" by hand.

Digit '2' maps to: "abc" Digit '3' maps to: "def"

I need all combinations:

Pick from digit 2    Pick from digit 3    Result
      a          +         d          =    "ad"
      a          +         e          =    "ae"
      a          +         f          =    "af"
      b          +         d          =    "bd"
      b          +         e          =    "be"
      b          +         f          =    "bf"
      c          +         d          =    "cd"
      c          +         e          =    "ce"
      c          +         f          =    "cf"

Total: 9 combinations (3 × 3)

Pattern: For each digit, try every letter it maps to.

---

Visualizing as Tree

For digits = "23":

                    ""
                    |
        -------------------------
        |           |           |
       "a"         "b"         "c"    ← digit 2
        |           |           |
    ---------   ---------   ---------
    |   |   |   |   |   |   |   |   |
   "ad""ae""af" "bd""be""bf" "cd""ce""cf"  ← digit 3

Leaf nodes = answer

At each level (digit), I make a choice (pick a letter).

---

Approach 1: Recursion (Backtracking)

Recursive Logic

At index i:
  - If i == length, we've built complete combination → add to result
  - Otherwise:
      Get letters for digits[i]
      For each letter:
        - Add letter to current
        - Recurse for index i+1
        - Remove letter (backtrack)

Code

import java.util.*;

class Solution {
    private List<String> result;
    private String[] mapping;

    public List<String> letterCombinations(String digits) {
        result = new ArrayList<>();

        if (digits == null || digits.length() == 0) {
            return result;
        }

        mapping = new String[] {
            "",     // 0
            "",     // 1
            "abc",  // 2
            "def",  // 3
            "ghi",  // 4
            "jkl",  // 5
            "mno",  // 6
            "pqrs", // 7
            "tuv",  // 8
            "wxyz"  // 9
        };

        backtrack(0, new StringBuilder(), digits);
        return result;
    }

    private void backtrack(int index, StringBuilder current, String digits) {
        // Base case
        if (index == digits.length()) {
            result.add(current.toString());
            return;
        }

        // Get letters for current digit
        String letters = mapping[digits.charAt(index) - '0'];

        // Try each letter
        for (int i = 0; i < letters.length(); i++) {
            char letter = letters.charAt(i);

            // Choose
            current.append(letter);

            // Explore
            backtrack(index + 1, current, digits);

            // Unchoose (backtrack)
            current.deleteCharAt(current.length() - 1);
        }
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.letterCombinations("23"));
        System.out.println(sol.letterCombinations(""));
        System.out.println(sol.letterCombinations("2"));
    }
}

Dry Run

digits = "23"

backtrack(0, "", "23"):
  index = 0, digit = '2', letters = "abc"

  i = 0, letter = 'a':
    current = "a"
    backtrack(1, "a", "23"):
      index = 1, digit = '3', letters = "def"

      i = 0, letter = 'd':
        current = "ad"
        backtrack(2, "ad", "23"):
          index = 2 == length → add "ad" ✓
        current = "a" (deleted 'd')

      i = 1, letter = 'e':
        current = "ae"
        backtrack(2, "ae", "23"):
          index = 2 == length → add "ae" ✓
        current = "a" (deleted 'e')

      i = 2, letter = 'f':
        current = "af"
        backtrack(2, "af", "23"):
          index = 2 == length → add "af" ✓
        current = "a" (deleted 'f')

    current = "" (deleted 'a')

  i = 1, letter = 'b':
    current = "b"
    backtrack(1, "b", "23"):
      index = 1, digit = '3', letters = "def"

      i = 0, letter = 'd':
        current = "bd"
        backtrack(2, "bd", "23"):
          index = 2 == length → add "bd" ✓
        current = "b"

      i = 1, letter = 'e':
        current = "be"
        backtrack(2, "be", "23"):
          index = 2 == length → add "be" ✓
        current = "b"

      i = 2, letter = 'f':
        current = "bf"
        backtrack(2, "bf", "23"):
          index = 2 == length → add "bf" ✓
        current = "b"

    current = "" (deleted 'b')

  i = 2, letter = 'c':
    current = "c"
    backtrack(1, "c", "23"):
      index = 1, digit = '3', letters = "def"

      i = 0, letter = 'd':
        current = "cd"
        backtrack(2, "cd", "23"):
          index = 2 == length → add "cd" ✓
        current = "c"

      i = 1, letter = 'e':
        current = "ce"
        backtrack(2, "ce", "23"):
          index = 2 == length → add "ce" ✓
        current = "c"

      i = 2, letter = 'f':
        current = "cf"
        backtrack(2, "cf", "23"):
          index = 2 == length → add "cf" ✓
        current = "c"

    current = "" (deleted 'c')

Result: ["ad","ae","af","bd","be","bf","cd","ce","cf"] ✓

Understanding Backtracking

The pattern:

current.append(letter);                    // Choose
backtrack(index + 1, current, digits);     // Explore
current.deleteCharAt(current.length() - 1); // Unchoose

Why unchoose?

After exploring with 'a', we need to try 'b'. But current still has 'a'! So we remove it to restore original state.

current = ""
Try 'a': current = "a" → explore all paths → current = "" (restore)
Try 'b': current = "b" → explore all paths → current = "" (restore)
Try 'c': current = "c" → explore all paths → current = "" (restore)

This is backtracking - undo choice to try next option.

Complexity

Time: O(4^n × n) - 4^n combinations (worst case, digits 7 and 9 have 4 letters) - n to build each string

Space: O(n) - Recursion depth = n

---

Approach 2: Iterative (BFS)

The Idea

Build combinations level by level using a queue.

For digits = "23":

Level 0: [""]

Level 1 (digit '2'):
  Take "", add 'a','b','c' → ["a", "b", "c"]

Level 2 (digit '3'):
  Take "a", add 'd','e','f' → ["ad", "ae", "af"]
  Take "b", add 'd','e','f' → ["bd", "be", "bf"]
  Take "c", add 'd','e','f' → ["cd", "ce", "cf"]
  Queue: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Code

import java.util.*;

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();

        if (digits == null || digits.length() == 0) {
            return result;
        }

        String[] mapping = new String[] {
            "",     // 0
            "",     // 1
            "abc",  // 2
            "def",  // 3
            "ghi",  // 4
            "jkl",  // 5
            "mno",  // 6
            "pqrs", // 7
            "tuv",  // 8
            "wxyz"  // 9
        };

        Queue<String> queue = new LinkedList<>();
        queue.offer("");

        for (int i = 0; i < digits.length(); i++) {
            String letters = mapping[digits.charAt(i) - '0'];
            int size = queue.size();

            for (int j = 0; j < size; j++) {
                String current = queue.poll();

                for (char letter : letters.toCharArray()) {
                    queue.offer(current + letter);
                }
            }
        }

        result.addAll(queue);
        return result;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.letterCombinations("23"));
    }
}

Dry Run

digits = "23"
queue = [""]

i = 0, digit = '2', letters = "abc", size = 1:
  j = 0:
    current = "" (poll)
    Add 'a': queue = ["a"]
    Add 'b': queue = ["a", "b"]
    Add 'c': queue = ["a", "b", "c"]

i = 1, digit = '3', letters = "def", size = 3:
  j = 0:
    current = "a" (poll)
    Add 'd': queue = ["b", "c", "ad"]
    Add 'e': queue = ["b", "c", "ad", "ae"]
    Add 'f': queue = ["b", "c", "ad", "ae", "af"]

  j = 1:
    current = "b" (poll)
    Add 'd': queue = ["c", "ad", "ae", "af", "bd"]
    Add 'e': queue = ["c", "ad", "ae", "af", "bd", "be"]
    Add 'f': queue = ["c", "ad", "ae", "af", "bd", "be", "bf"]

  j = 2:
    current = "c" (poll)
    Add 'd': queue = ["ad", "ae", "af", "bd", "be", "bf", "cd"]
    Add 'e': queue = ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce"]
    Add 'f': queue = ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

Result: ["ad","ae","af","bd","be","bf","cd","ce","cf"] ✓

Complexity

Time: O(4^n × n) Space: O(4^n) - Queue holds all combinations

---

Comparison

┌─────────────┬──────────────┬──────────────┐
│ Aspect      │ Recursion    │ Iteration    │
├─────────────┼──────────────┼──────────────┤
│ Time        │ O(4^n × n)   │ O(4^n × n)   │
│ Space       │ O(n)         │ O(4^n)       │
│ Code        │ Shorter      │ Longer       │
│ Natural     │ Yes ✓        │ No           │
│ Interview   │ Preferred ✓  │ Alternative  │
└─────────────┴──────────────┴──────────────┘

Recommendation: Use recursion (backtracking) as primary approach.

---

Quick Revision

Quick Implementation

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution {
  public List<String> letterCombinations(String letters) {
    HashMap<Integer, String> map = new HashMap<>();
    map.put(0, "");
    map.put(1, "");
    map.put(2, "abc");
    map.put(3, "def");
    map.put(4, "ghi");
    map.put(5, "jkl");
    map.put(6, "mno");
    map.put(7, "pqrs");
    map.put(8, "tuv");
    map.put(9, "wxyz");

    // return recursive(letters, map);

    return iterative(letters, map);
  }

  private List<String> iterative(String letters, HashMap<Integer, String> map) {
    // step 1: create a queue and add empty for now
    Queue<String> queue = new LinkedList<>();
    queue.offer("");

    // step 2: kind of algo or step to remember only.
    // everytime take next letter from "letters", for example, 2 from 23.
    // everytime take 1 from queue and append with all chars from "2" and add to
    // queue
    for (int i = 0; i < letters.length(); i++) {
      // for i = 0, "abc" for 2
      // for i = 1, "def" for 3
      String mapping = map.get(letters.charAt(i) - '0');
      // for i = 0, len becomes 0 and polled is ""
      // for i = 1, len becomes 3 and polled are "a", "b" and "c"
      int len = queue.size();

      while (len > 0) {
        String polled = queue.poll();

        // step 3: combine every letter from mapping with polled item
        for (int j = 0; j < mapping.length(); j++) {
          // for i = 0, "a", "b", "c" gets polled to queue.
          queue.offer(polled.concat(String.valueOf(mapping.charAt(j))));
        }

        len--;
      }
    }

    // step 4: put remaining items on the queue to res list which is the result
    List<String> res = new ArrayList<>();
    while (!queue.isEmpty()) {
      res.add(queue.poll());
    }

    return res;
  }

  private List<String> recursive(String letters, HashMap<Integer, String> map) {
    List<String> res = new ArrayList<>();

    recursiveUtil(letters, map, 0, new StringBuilder(), res);

    return res;
  }

  private void recursiveUtil(String letters, HashMap<Integer, String> map, int currIndex, StringBuilder currString,
      List<String> res) {
    // step 5: base case
    if (currIndex == letters.length()) {
      res.add(currString.toString());

      return;
    }

    // step 1: iterate all characters of the digit.
    // for example, in "23", for 2, here you need to loop for "abc"
    // when "a" is done in first iteration, go for next index which is "3" and there
    // we need to loop for "def" and hence it will become "ad", "ae" and "af"
    // in "23" with currIndex as 0
    // letters.charAt(currIndex) => "23".charAt(0) => ascii(2) - '0' => 2 => "abc"
    String mapping = map.get(letters.charAt(currIndex) - '0');

    for (int i = 0; i < mapping.length(); i++) {
      // step 2: add a
      currString.append(mapping.charAt(i));

      // step 3: proceed for next letter from the next digit
      recursiveUtil(letters, map, currIndex + 1, currString, res);

      // step 4: remove a from curr / temp
      currString.deleteCharAt(currString.length() - 1);
    }
  }

  public static void main(String[] args) {
    Solution s = new Solution();
    System.out
        .println(s.letterCombinations("23").equals(List.of("ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf")));
  }
}

---

Summary

Backtracking Pattern:

void backtrack(state) {
    if (goal reached) {
        add to result
        return
    }

    for each choice {
        make choice
        backtrack(next state)
        undo choice
    }
}

Key Insight: Backtracking explores all possibilities by trying each choice, exploring recursively, then undoing to try next choice.

This is the foundation for all backtracking problems! ✓