Skip to main content

36. Letter Combinations of a Phone Number

mediumAsked at Ola

Return all possible letter combinations that a phone number string could represent.

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. The mapping is the classic phone keypad: 2->abc, 3->def, ..., 9->wxyz.

Constraints

  • 0 <= digits.length <= 4
  • digits[i] is 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. Iterative product

Start with [''], multiply by letters for each digit.

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

Tradeoff:

2. DFS backtracking

Recursively build a combination; when index hits length, push the path.

Time
O(3^n * n)
Space
O(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'};
  const out = [];
  const dfs = (i, path) => {
    if (i === digits.length) { out.push(path); return; }
    for (const c of map[digits[i]]) dfs(i+1, path+c);
  };
  dfs(0, '');
  return out;
}

Tradeoff:

Ola-specific tips

Ola uses this to verify clean recursion structure; tie it to enumerating short driver-promo codes from a fixed keypad alphabet.

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 Ola interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →