Skip to main content

18. Letter Combinations of a Phone Number

mediumAsked at Gojek

Return every possible letter combination the digit string could represent on a phone keypad.

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

Problem

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

Constraints

  • 0 <= digits.length <= 4
  • digits[i] is in the range ['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 an empty seed; for each digit cross-multiply current strings with that digit's letters.

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

Tradeoff:

2. Backtracking

Recurse digit by digit, building the current string; emit when length matches digits length. Same complexity, cleaner stack frame model.

Time
O(4^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:

Gojek-specific tips

Gojek favors explicit recursion when the branching factor is small because their multi-service feature flags read more like a config-tree walk than a number-cruncher.

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

Practice these live with InterviewChamp.AI →