Letter Combinations of a Phone Number
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"]
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;}