Phone Keypad Letter Combinations

You're in a technical phone screen with Apple, and the interviewer opens with a fitting question: "You know how the old phone keypads mapped digits to letters? Given a string of digits, can you generate all the letter combinations those digits could represent?" It's a question that has appeared in Apple interviews 24 times in recent data alone, and it's just as popular at Adobe, Google, Amazon, and DE Shaw. The reason is simple: it tests whether you can think recursively and apply backtracking, two skills that transfer directly to harder combinatorial problems.

TL;DR

Map each digit (2-9) to its corresponding letters using a hash map. Use backtracking to explore every combination: at each digit, iterate through its letters, append one to the current path, recurse on the next digit, then remove the letter and try the next one. When the path length equals the number of digits, add it to the result. This runs in O(4^n) time and space, where n is the number of input digits. The 4 comes from digits 7 and 9 mapping to four letters each.

Why This Problem Matters

Phone keypad letter combinations is often the first backtracking problem candidates encounter. It strips away the complexity of pruning and constraint checking that harder problems like N-Queens or Sudoku require, and lets you focus purely on the recursive structure of generating combinations. Once this pattern clicks, you can apply the same template to permutations, subsets, combination sums, and dozens of other problems.

The Phone Keypad Mapping

Before writing any code, we need the digit-to-letter mapping that every phone from the 1990s had printed on its buttons. Digit 1 maps to nothing, digits 2 through 9 each map to three or four letters:

Note that digits 7 and 9 map to four letters (pqrs and wxyz), while the rest map to three. This asymmetry is why the worst-case complexity uses 4 as the branching factor rather than 3.

Understanding the Problem

Given: A string of digits from 2-9 (e.g., "23") Return: All possible letter combinations those digits could represent Order: The result can be in any order

For "23", digit 2 maps to "abc" and digit 3 maps to "def". Every letter from the first digit can pair with every letter from the second digit, producing 3 x 3 = 9 combinations:

letterCombinations("23") => ["ad","ae","af","bd","be","bf","cd","ce","cf"]
letterCombinations("")   => []
letterCombinations("2")  => ["a","b","c"]

Edge Cases

1. Empty string: Return an empty list (not a list containing an empty string)
2. Single digit: Return just the letters for that digit
3. Digits 7 or 9: These produce four letters per digit instead of three
4. Maximum length (4 digits): Up to 4^4 = 256 combinations

Solution Approach

The core idea is to build each combination one letter at a time, choosing a letter for the current digit, then moving to the next digit. When you have chosen a letter for every digit, you have a complete combination.

This is textbook backtracking:

Visualizing the Recursion Tree

For input "23", the recursion tree has the root at index 0. At the first level, we branch into three children (one per letter of digit 2). At the second level, each of those branches into three more children (one per letter of digit 3). The leaves are the complete combinations:

Each root-to-leaf path through this tree represents one combination. The total number of leaves is 3 * 3 = 9, matching our expected output.

The Backtracking Process

Tracing the first few steps for "23":

After adding "ad" to the result, the algorithm removes "d" from the path (backtracking to "a"), then tries "e" to produce "ae", then "f" for "af". Once all letters for digit 3 are exhausted with prefix "a", it backtracks further, removes "a", and picks "b" to start the next branch.

Result Accumulation

As the recursion explores every branch, each leaf node appends one combination to the result:

Implementation

Prefer a different language? Jump to solutions in other languages.

Here is the Java solution with detailed explanations:

import java.util.*;

public class Solution {

  public List<String> letterCombinations(String digits) {
    // Handle the empty input edge case
    if (digits == null || digits.isEmpty()) {
      return new ArrayList<>();
    }

    // Build the digit-to-letter mapping
    Map<Character, String> phoneMap = new HashMap<>();
    phoneMap.put('2', "abc");
    phoneMap.put('3', "def");
    phoneMap.put('4', "ghi");
    phoneMap.put('5', "jkl");
    phoneMap.put('6', "mno");
    phoneMap.put('7', "pqrs");
    phoneMap.put('8', "tuv");
    phoneMap.put('9', "wxyz");

    List<String> result = new ArrayList<>();
    backtrack(result, phoneMap, digits, 0, new StringBuilder());
    return result;
  }

  private void backtrack(List<String> result, Map<Character, String> phoneMap,
                          String digits, int index, StringBuilder current) {
    // Base case: we have chosen a letter for every digit
    if (index == digits.length()) {
      result.add(current.toString());
      return;
    }

    // Get the letters for the current digit
    String letters = phoneMap.get(digits.charAt(index));

    // Try each letter as the next character in our combination
    for (char letter : letters.toCharArray()) {
      current.append(letter);              // Choose
      backtrack(result, phoneMap, digits, index + 1, current);  // Explore
      current.deleteCharAt(current.length() - 1);               // Un-choose
    }
  }
}

The three-step pattern inside the loop is the heart of backtracking:

1. Choose: Append the current letter to the path
2. Explore: Recurse on the next digit
3. Un-choose: Remove the letter so the next iteration starts clean

The StringBuilder approach modifies one object in place rather than creating new strings at each level. The deleteCharAt call is what makes this backtracking - it restores the state before trying the next option.

Why StringBuilder Matters in Java

Java strings are immutable. Without StringBuilder, each current + letter would allocate a new String object. At depth n, that means n allocations per recursive call. StringBuilder gives O(1) append and delete, which keeps the overhead per recursive step constant.

In Python and JavaScript, the idiomatic approach is path + letter, which creates a new string implicitly. This is fine because those languages optimize short string concatenation internally, and the new string acts as an automatic "undo" when the recursive call returns. No explicit backtracking step is needed.

Complexity Analysis

Time Complexity: O(4^n)

Each digit branches into 3 or 4 recursive calls. In the worst case (all digits are 7 or 9), each digit produces 4 branches. With n digits, we visit up to 4^n leaf nodes, and building each combination string takes O(n) work. The total is O(n * 4^n), but since the constraint limits n to at most 4, the n factor is bounded by a small constant.

Space Complexity: O(4^n)

The output list stores up to 4^n strings, each of length n. The recursion stack uses O(n) space, but the output dominates. If you exclude the output (which interviewers sometimes ask about), the auxiliary space is just O(n) for the recursion depth and the current path.

Digits 7 and 9 Produce Four Branches

Most digits map to three letters, but 7 (pqrs) and 9 (wxyz) map to four:

This is why the complexity bound uses 4 rather than 3. For input "79", there are 4 * 4 = 16 combinations instead of the 3 * 3 = 9 you would get for "23".

Common Pitfalls

1. Returning [""] instead of [] for empty input: An empty string means no digits were pressed, so no combinations exist. Returning a list containing an empty string is incorrect.

2. Forgetting to backtrack: If using a mutable structure like StringBuilder in Java, you must remove the last character after the recursive call. Without this, subsequent iterations append to a corrupted path.

3. Hardcoding three letters per digit: Digits 7 and 9 have four letters. The algorithm handles this naturally if you iterate over the mapped string rather than assuming a fixed count.

4. Using the wrong mapping: Double-check that your map matches the standard phone keypad. A common mistake is mapping digit 1 (which has no letters) or getting the letter ranges wrong.

Interview Tips

When solving this problem in an interview:

1. Start by writing out the mapping. This anchors the conversation and shows you understand the input format. Mention that 7 and 9 have four letters.

2. Draw the recursion tree for a small example. Sketching the tree for "23" on the whiteboard makes the branching factor and base case obvious.

3. Name the three backtracking steps. Saying "choose, explore, un-choose" signals that you recognize the pattern and can apply it to other problems.

4. Discuss the iterative alternative. After presenting the recursive solution, briefly mention that you could also solve this iteratively by building combinations level by level (BFS-style). Interviewers appreciate seeing that you know multiple approaches.

5. State the complexity clearly. Say "O(4^n) time and space because digits 7 and 9 map to four letters, giving a worst-case branching factor of 4."

Key Takeaways

• Phone keypad letter combinations is a pure backtracking problem with no pruning required, making it one of the cleanest examples of the "choose, explore, un-choose" template.
• The digit-to-letter mapping is stored in a hash map (or array). Digits 7 and 9 have four letters each, giving O(4^n) worst-case complexity rather than O(3^n).
• In Java, use StringBuilder with explicit deleteCharAt for backtracking. In Python and JavaScript, string concatenation (path + letter) implicitly creates a new path, so no manual undo is needed.
• The base case triggers when the current index equals the length of the input string, meaning a letter has been chosen for every digit.
• Always return an empty list for empty input, not a list containing an empty string.

Practice Makes Perfect

Once you are comfortable with phone keypad letter combinations, try these related backtracking problems to solidify the pattern:

• Generate all permutations of a list of numbers
• Generate all subsets (power set) of a collection
• Combination sum (find combinations that add up to a target)
• N-Queens (place queens on a board with constraint checking)

Remember, consistent practice is the key to succeeding in coding interviews. This problem and thousands of others are available on Firecode, where over 50,000 users have successfully prepared for technical interviews and landed six and seven-figure jobs at top tech companies. Whether you are just starting or preparing for your dream job, mastering backtracking fundamentals like this will serve you well.

Happy coding!

Solutions in Other Languages

Python

from typing import List

class Solution:
    def letter_combinations(self, digits: str) -> List[str]:
        if not digits:
            return []

        digit_to_char = {
            '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
            '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
        }

        def backtrack(index: int, path: str):
            if index == len(digits):
                combinations.append(path)
                return
            possible_letters = digit_to_char[digits[index]]
            for letter in possible_letters:
                backtrack(index + 1, path + letter)

        combinations = []
        backtrack(0, "")
        return combinations

Python's string concatenation (path + letter) creates a new string on each recursive call, so the old path is preserved when the call returns. No explicit backtracking step is needed.

JavaScript

class Solution {
  letterCombinations(digits) {
    if (!digits) return [];

    const digitToLetters = {
      '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
      '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
    };

    const result = [];

    const backtrack = (index, path) => {
      if (index === digits.length) {
        result.push(path);
        return;
      }
      const letters = digitToLetters[digits[index]];
      for (let letter of letters) {
        backtrack(index + 1, path + letter);
      }
    };

    backtrack(0, '');
    return result;
  }
}

Like Python, JavaScript uses string concatenation for implicit backtracking. The closure captures result and digitToLetters naturally.

TypeScript

class Solution {
  letterCombinations(digits: string): string[] {
    if (!digits) return [];

    const digitToLetters: Record<string, string> = {
      '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
      '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
    };

    const result: string[] = [];

    const backtrack = (index: number, path: string): void => {
      if (index === digits.length) {
        result.push(path);
        return;
      }
      const letters = digitToLetters[digits[index]];
      for (const letter of letters) {
        backtrack(index + 1, path + letter);
      }
    };

    backtrack(0, '');
    return result;
  }
}

C++

#include <vector>
#include <string>
#include <functional>
#include <unordered_map>

class Solution {
public:
  std::vector<std::string> letterCombinations(std::string &digits) {
    if (digits.empty()) return {};

    std::unordered_map<char, std::string> digitToLetters = {
      {'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"},
      {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}
    };

    std::vector<std::string> result;
    std::string currentCombination;

    std::function<void(int)> backtrack = [&](int index) {
      if (index == digits.size()) {
        result.push_back(currentCombination);
        return;
      }
      char digit = digits[index];
      const std::string &letters = digitToLetters[digit];
      for (char letter : letters) {
        currentCombination.push_back(letter);
        backtrack(index + 1);
        currentCombination.pop_back();
      }
    };

    backtrack(0);
    return result;
  }
};

The C++ solution uses a lambda that captures result, currentCombination, digitToLetters, and digits by reference. push_back and pop_back on std::string give O(1) append and backtrack.

Go

package solution

func (s *Solution) LetterCombinations(digits string) []string {
    if len(digits) == 0 {
        return []string{}
    }

    digitToLetters := map[byte]string{
        '2': "abc", '3': "def", '4': "ghi", '5': "jkl",
        '6': "mno", '7': "pqrs", '8': "tuv", '9': "wxyz",
    }

    var result []string
    var backtrack func(index int, path string)
    backtrack = func(index int, path string) {
        if index == len(digits) {
            result = append(result, path)
            return
        }
        letters := digitToLetters[digits[index]]
        for i := 0; i < len(letters); i++ {
            backtrack(index+1, path+string(letters[i]))
        }
    }

    backtrack(0, "")
    return result
}

type Solution struct{}

Go uses string concatenation (path + string(letters[i])) for implicit backtracking. The recursive function is declared as a variable so it can reference itself within the closure.

Scala

class Solution {
  def letterCombinations(digits: String): List[String] = {
    if (digits.isEmpty) return List()

    val digitToLetters = Map(
      '2' -> "abc", '3' -> "def", '4' -> "ghi", '5' -> "jkl",
      '6' -> "mno", '7' -> "pqrs", '8' -> "tuv", '9' -> "wxyz"
    )

    def backtrack(index: Int, path: String, combinations: List[String]): List[String] = {
      if (index == digits.length) {
        return path :: combinations
      }
      val letters = digitToLetters(digits(index))
      letters.foldRight(combinations) { (letter, acc) =>
        backtrack(index + 1, path + letter, acc)
      }
    }

    backtrack(0, "", List())
  }
}

The Scala solution uses foldRight to accumulate results in a purely functional style. Each letter at the current digit produces a recursive call, and results are prepended to the accumulator.

Kotlin

class Solution {
  fun letterCombinations(digits: String): List<String> {
    if (digits.isEmpty()) {
      return emptyList()
    }

    val phoneMap = mapOf(
      '2' to "abc", '3' to "def", '4' to "ghi", '5' to "jkl",
      '6' to "mno", '7' to "pqrs", '8' to "tuv", '9' to "wxyz"
    )

    val result = mutableListOf<String>()
    backtrack(result, phoneMap, digits, 0, StringBuilder())
    return result
  }

  private fun backtrack(
    result: MutableList<String>, phoneMap: Map<Char, String>,
    digits: String, index: Int, current: StringBuilder
  ) {
    if (index == digits.length) {
      result.add(current.toString())
      return
    }
    val letters = phoneMap[digits[index]] ?: return
    for (letter in letters) {
      current.append(letter)
      backtrack(result, phoneMap, digits, index + 1, current)
      current.deleteCharAt(current.lastIndex)
    }
  }
}

Ruby

class Solution
  def letter_combinations(digits)
    return [] if digits.nil? || digits.empty?

    phone_map = {
      '2' => 'abc', '3' => 'def', '4' => 'ghi', '5' => 'jkl',
      '6' => 'mno', '7' => 'pqrs', '8' => 'tuv', '9' => 'wxyz'
    }

    result = []
    backtrack(result, phone_map, digits, 0, '')
    result
  end

  def backtrack(result, phone_map, digits, index, current)
    if index == digits.length
      result << current
      return
    end
    letters = phone_map[digits[index]]
    letters.each_char do |letter|
      backtrack(result, phone_map, digits, index + 1, current + letter)
    end
  end
end

Rust

use std::collections::HashMap;

pub struct Solution;

impl Solution {
    pub fn letter_combinations(&self, digits: String) -> Vec<String> {
        if digits.is_empty() {
            return Vec::new();
        }

        let mut phone_map = HashMap::new();
        phone_map.insert('2', "abc");
        phone_map.insert('3', "def");
        phone_map.insert('4', "ghi");
        phone_map.insert('5', "jkl");
        phone_map.insert('6', "mno");
        phone_map.insert('7', "pqrs");
        phone_map.insert('8', "tuv");
        phone_map.insert('9', "wxyz");

        let mut result = Vec::new();
        Self::backtrack(&mut result, &phone_map, &digits, 0, &mut String::new());
        result
    }

    fn backtrack(
        result: &mut Vec<String>, phone_map: &HashMap<char, &str>,
        digits: &str, index: usize, current: &mut String
    ) {
        if index == digits.len() {
            result.push(current.clone());
            return;
        }
        let letters = phone_map[&digits.chars().nth(index).unwrap()];
        for letter in letters.chars() {
            current.push(letter);
            Self::backtrack(result, phone_map, digits, index + 1, current);
            current.pop();
        }
    }
}

Rust requires explicit ownership management. The current string is passed as &mut String, and current.clone() creates a snapshot when the combination is complete. push and pop handle the backtracking.

Swift

import Foundation

class Solution {
    func letterCombinations(_ digits: String) -> [String] {
        if digits.isEmpty { return [] }

        let phoneMap: [Character: String] = [
            "2": "abc", "3": "def", "4": "ghi", "5": "jkl",
            "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"
        ]

        var result: [String] = []
        let digitsArray = Array(digits)
        backtrack(&result, phoneMap, digitsArray, 0, "")
        return result
    }

    private func backtrack(
        _ result: inout [String], _ phoneMap: [Character: String],
        _ digits: [Character], _ index: Int, _ current: String
    ) {
        if index == digits.count {
            result.append(current)
            return
        }
        guard let letters = phoneMap[digits[index]] else { return }
        for letter in letters {
            backtrack(&result, phoneMap, digits, index + 1, current + String(letter))
        }
    }
}

C#

using System.Collections.Generic;
using System.Text;

public class Solution {
    public List<string> LetterCombinations(string digits) {
        if (digits == null || digits.Length == 0) {
            return new List<string>();
        }

        var phoneMap = new Dictionary<char, string>();
        phoneMap['2'] = "abc"; phoneMap['3'] = "def";
        phoneMap['4'] = "ghi"; phoneMap['5'] = "jkl";
        phoneMap['6'] = "mno"; phoneMap['7'] = "pqrs";
        phoneMap['8'] = "tuv"; phoneMap['9'] = "wxyz";

        var result = new List<string>();
        Backtrack(result, phoneMap, digits, 0, new StringBuilder());
        return result;
    }

    private void Backtrack(
        List<string> result, Dictionary<char, string> phoneMap,
        string digits, int index, StringBuilder current
    ) {
        if (index == digits.Length) {
            result.Add(current.ToString());
            return;
        }
        var letters = phoneMap[digits[index]];
        foreach (var letter in letters) {
            current.Append(letter);
            Backtrack(result, phoneMap, digits, index + 1, current);
            current.Remove(current.Length - 1, 1);
        }
    }
}

Dart

class Solution {
  List<String> letterCombinations(String digits) {
    if (digits.isEmpty) { return []; }

    Map<String, String> phoneMap = {
      '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
      '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz',
    };

    List<String> result = [];
    _backtrack(result, phoneMap, digits, 0, []);
    return result;
  }

  void _backtrack(
    List<String> result, Map<String, String> phoneMap,
    String digits, int index, List<String> current
  ) {
    if (index == digits.length) {
      result.add(current.join());
      return;
    }
    String letters = phoneMap[digits[index]]!;
    for (String letter in letters.split('')) {
      current.add(letter);
      _backtrack(result, phoneMap, digits, index + 1, current);
      current.removeLast();
    }
  }
}

PHP

<?php

class Solution {
    public function letterCombinations(string $digits): array {
        if ($digits === "") { return []; }

        $phoneMap = [
            '2' => 'abc', '3' => 'def', '4' => 'ghi', '5' => 'jkl',
            '6' => 'mno', '7' => 'pqrs', '8' => 'tuv', '9' => 'wxyz'
        ];

        $result = [];
        $this->backtrack($result, $phoneMap, $digits, 0, "");
        return $result;
    }

    private function backtrack(
        array &$result, array $phoneMap,
        string $digits, int $index, string $current
    ): void {
        if ($index === strlen($digits)) {
            $result[] = $current;
            return;
        }
        $letters = $phoneMap[$digits[$index]];
        for ($i = 0; $i < strlen($letters); $i++) {
            $this->backtrack($result, $phoneMap, $digits, $index + 1, $current . $letters[$i]);
        }
    }
}