Skip to main content

21. Letter Combinations of a Phone Number

mediumAsked at Udemy

Generate all letter combinations from phone-pad digits — Udemy uses this backtracking warm-up before harder search autocomplete and tag-generation problems.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given a string containing digits from 2-9, return all possible letter combinations that the number could represent using the phone keypad mapping. Return the answers in any order.

Constraints

  • 0 <= digits.length <= 4
  • digits[i] is a digit in ['2','9']

Examples

Example 1

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

Example 2

Input
digits = ""
Output
[]

Approaches

1. Brute force iterative

Start with [''] and for each digit cross-product the existing results with each letter — correct but less elegant than recursion.

Time
O(4^n * n)
Space
O(4^n * n)
function letterCombinations(digits) {
  if (!digits) return [];
  const map = {'2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'};
  let res = [''];
  for (const d of digits)
    res = res.flatMap(p => map[d].split('').map(c => p + c));
  return res;
}

Tradeoff:

2. Backtracking DFS

Build combinations character by character with a DFS helper; push to results only when path length equals digits length.

Time
O(4^n * n)
Space
O(n)
function letterCombinations(digits) {
  if (!digits.length) return [];
  const map = {'2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'};
  const res = [];
  function bt(i, path) {
    if (i === digits.length) { res.push(path); return; }
    for (const c of map[digits[i]]) bt(i+1, path+c);
  }
  bt(0, '');
  return res;
}

Tradeoff:

Udemy-specific tips

Udemy asks about e-learning recommendation systems, content search, and marketplace algorithms — balanced mix of arrays, hash maps, and dynamic programming problems.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Letter Combinations of a Phone Number and other Udemy interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →