Letter Combinations of a Phone Number…

Approach Summary

Backtracking: for each digit, try each mapped letter and recurse on the remaining digits. Collect results at leaf nodes.

Full Solution & Approach

Each digit maps to a fixed set of letters, and a complete combination is formed by choosing exactly one letter per digit, in order. The number of combinations is the product of the map sizes — 3 or 4 choices per position — so enumerate them with backtracking. A recursive function receives the current digit index and the path of chosen letters so far. When the index reaches the length of the digits string, the path is a complete combination, so record it. Otherwise, for every letter in the mapping of the current digit, append it, recurse on the next index, and pop it back off. The pop restores the path so every branch shares one buffer instead of copying strings at every step. The search tree has depth equal to the number of digits and branching factor 3 or 4, so the total output size is bounded by 4^len. The empty-digits case must return an empty list, not a list containing an empty string — a common off-by-one. This problem is the simplest member of the digits-mapping family that also includes generate-parentheses and IP-address restoration.

The output contains at most 4^len strings, each of length len, so time and space are O(len · 4^len) in the worst case — this is output-bound and unavoidable.

Solution Code

Solution

def letter_combinations(digits: str) -> list[str]:
    if not digits:
        return []
    mapping = {
        '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
        '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz',
    }
    res = []

    def backtrack(i: int, path: list[str]) -> None:
        if i == len(digits):
            res.append(''.join(path))
            return
        for ch in mapping[digits[i]]:
            path.append(ch)
            backtrack(i + 1, path)
            path.pop()

    backtrack(0, [])
    return res

function letterCombinations(digits) {
  if (!digits) return [];
  const map = { 2: 'abc', 3: 'def', 4: 'ghi', 5: 'jkl', 6: 'mno', 7: 'pqrs', 8: 'tuv', 9: 'wxyz' };
  const res = [];
  function backtrack(i, path) {
    if (i === digits.length) {
      res.push(path.join(''));
      return;
    }
    for (const ch of map[digits[i]]) {
      path.push(ch);
      backtrack(i + 1, path);
      path.pop();
    }
  }
  backtrack(0, []);
  return res;
}

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(digits, map, 0, new StringBuilder(), res);
    return res;
}

private void backtrack(String digits, String[] map, int i, StringBuilder path, List<String> res) {
    if (i == digits.length()) {
        res.add(path.toString());
        return;
    }
    for (char ch : map[digits.charAt(i) - '0'].toCharArray()) {
        path.append(ch);
        backtrack(digits, map, i + 1, path, res);
        path.deleteCharAt(path.length() - 1);
    }
}

vector<string> letterCombinations(const string& digits) {
    if (digits.empty()) return {};
    vector<string> map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    vector<string> res;
    string path;
    backtrack(digits, map, 0, path, res);
    return res;
}

void backtrack(const string& digits, const vector<string>& map, int i, string& path, vector<string>& res) {
    if (i == (int)digits.size()) {
        res.push_back(path);
        return;
    }
    for (char ch : map[digits[i] - '0']) {
        path.push_back(ch);
        backtrack(digits, map, i + 1, path, res);
        path.pop_back();
    }
}

Edge Cases to Watch

Empty input — return [] (not [""])
Digits containing 7 or 9 — their 4-letter maps make the output up to 4x larger
Digits with a single 1 or 0 — no letters; the standard mapping treats them as empty
Single digit — returns the letters of that digit as single characters

How to Recognize This Pattern

"All combinations of letters from phone number"
Classic backtracking: build combination letter by letter

Complexity Analysis

Time Complexity

O(4ⁿ × n)

Space Complexity

O(n)

Letter Combinations of a Phone Number