Letter Combinations of a Phone Number

New·#17·Medium·Recursion

Every string a digit sequence can spell

Asked at:AmazonGoogleMicrosoftMeta

Practice mode

Step

Initialization

Build the answer letter by letter. At digit i, branch once per letter in its keypad group and recurse on digit i+1. When the digits run out, the accumulated string is a finished combination — that is the base case at the leaves.

Recursion workspace

Backtracking

Step 1 / 46init

100%

digits

"23"

fn(0, "")

2 → abc 3 → def

ans

empty

Explanation

Keypad: 2 → abc 3 → def. Each digit branches across its letters; a full path down the tree spells one combination.

step 1 / 46

Space play← → stepHome reset

TimeO(4ⁿ · n)·SpaceO(n)

Backtracking

1const map = ["", "", "abc", "def", "ghi",
2             "jkl", "mno", "pqrs", "tuv", "wxyz"];
3 
4function helper(digits, ans, index, current) {
5  // Base case: every digit has contributed a letter
6  if (index === digits.length) {
7    ans.push(current);
8    return;
9  }
10 
11  // Letters available for this digit
12  const s = map[digits[index] - '0'];
13 
14  for (let i = 0; i < s.length; i++) {
15    helper(digits, ans, index + 1, current + s[i]);
16  }
17}//digits: 23count: 0
18 
19function letterCombinations(digits) {
20  const ans = [];
21  if (digits.length === 0) return ans;
22  helper(digits, ans, 0, "");
23  return ans;
24}

digits23

count0

Command Palette

Letter Combinations of a Phone Number

Letter Combinations of a Phone Number