Letter Combinations of a Phone Number Medium 0 attempts
LeetCode ↗

Letter Combinations of a Phone Number

Medium Stack&Queue LeetCode

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. The mapping of digit to letters is the same as on telephone buttons (2->abc, 3->def, ..., 9->wxyz). Return the answer in any order. If the input string is empty, return an empty array.

Example 1:

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

Example 2:

Input: digits = ""
Output: []
Sample Input
—
Sample Output
—
Constraints
  • 0 <= digits.length <= 4
  • digits[i] is in range ['2', '9']
Test Cases
Case 1
Args: ["23"] Expected: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Topics
Stack&Queue

Approach: Backtracking

Map each digit to its corresponding letters. Recursively build combinations by choosing one letter per digit and advancing to the next digit. When the current combination length equals the digits length, add it to the result.

function letterCombinationsOfAPhoneNumber(digits) {
  if (!digits.length) return [];
  const map = {2:"abc",3:"def",4:"ghi",5:"jkl",6:"mno",7:"pqrs",8:"tuv",9:"wxyz"};
  const result = [];
  function backtrack(i, curr) {
    if (i === digits.length) { result.push(curr); return; }
    for (const ch of map[digits[i]]) backtrack(i + 1, curr + ch);
  }
  backtrack(0, "");
  return result;
}

Time Complexity: O(4^n) where n is the length of digits

Space Complexity: O(n) for recursion depth

Saved in this browser only. Private to you.

JavaScript