Letter Combinations of a Phone Number

Medium

Problem

Given a string of digits 2–9, return every letter combination they could represent on a phone keypad (2 = abc, 3 = def, …, 9 = wxyz).

Example 1

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

Test cases

Case 1

Input:    "23"
Expected (any order): ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Case 2

Input:    ""
Expected (any order): []

Case 3

Input:    "2"
Expected (any order): ["a","b","c"]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Backtracking over digits

Time O(4^n · n)Space O(n)

One recursion level per digit, one branch per letter on that key.

function letterCombinations(digits) {
if (!digits) return [];
const map = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz'];
const res = [];
const bt = (i, cur) => {
if (i === digits.length) { res.push(cur); return; }
for (const ch of map[digits[i]]) bt(i + 1, cur + ch);
};
bt(0, '');
return res;
}